문제 링크
문제
티어: 골드 3
알고리즘: 그리디, 정렬
Alice 와 Bob 두 해적은 최근 보물섬에서 엄청난 양의 보물을 발견했다. 총 N개의 보물 상자를 발견했는데, 공평하게 번갈아가며 보물 상자를 하나씩 골라 가지기로 하였다. 각 보물 상자의 가치는 객관적으로 정하기 어렵기 때문에 두 사람 모두 자신이 생각하는 가치가 얼마인지 적어서 서로에게 공유했다. 즉, i번째 보물 상자는 Alice에겐 A[i] 달러 만큼의 가치를 갖고 Bob에겐 B[i] 달러 만큼의 가치를 갖는다. 상자를 나누어 갖기 위해 Alice부터 시작하여 Alice와 Bob은 번갈아가며 남은 상자들 중 하나를 가져가기로 했다. 상자를 하나 가져오면 상대방의 차례가 되며, N개의 상자가 모두 주인을 찾은 후 둘은 각자 갈 길을 떠나기로 했다.
편의상 보물 상자를 모두 나눈 후 Alice가 가져간 상자의 (Alice 기준대로의) 가치의 총합을 ScoreA라 하고 Bob이 가져간 상자의 (Bob 기준대로의) 가치의 총합을 ScoreB라 하자. Alice와 Bob은 서로 약속은 지키는 의리있는 해적이지만, 욕심이 많기 때문에 Alice의 목표는 (ScoreA - ScoreB)가 최대가 되도록 상자를 선택하는 것이고 Bob의 목표는 (ScoreB - ScoreA)가 최대가 되도록 상자를 선택하는 것이다.
이 두 사람은 언제나 최선을 다해서 어떤 상자를 가져갈지 결정한다.
예를 들어 N = 3 인 경우 세 개의 보물 상자가 있으며, 각 해적이 생각하는 보물 상자의 가치는 아래와 같다.
- 상자1: A[1] = 10, B[1] = 5
- 상자2: A[2] = 100, B[2] = 90
- 상자 3: A[3] = 2, B[3] = 0
이 때 Alice가 상자 2를 먼저 가져가고, 그 후 Bob이 상자 1을 가져간 후, 마지막으로 Alice가 상자 3을 가져간다면, Alice는 총 102 달러 만큼 보물을 챙기고 Bob은 총 5달러 만큼 보물을 챙기게 된다. 만약 Alice가 자신의 첫 차례에 상자 2가 아닌 다른 상자를 가져간다면 (상자 1 혹은 상자 3), Bob은 자신의 차례에 상자 2를 가져갈테니, 이 경우 Alice는 10+2 = 12 달러 그리고 Bob은 90달러 만큼의 보물을 챙기게 된다. 따라서 Alice가 최선을 다한다면 첫 차례에 반드시 보물 2를 가져가야 한다.
보물 상자의 수 N과 해적 둘이 각자 생각하는 보물 상자의 가치가 주어졌을 때, 두 사람이 최선을 다해 각자의 목표를 최대화 했을 때 (ScoreA - ScoreB) 값이 무엇인지 구하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스에 대해 첫 줄에 정수 N이 주어지며 이는 보물 상자의 수를 나타낸다.
다음 N줄에 걸쳐서 각 보물의 가치가 공백으로 구분되어 주어진다 (첫 수는 Alice가 생각하는 가치, 두 번째 수는 Bob이 생각하는 가치).
출력
각 테스트 케이스에 대하여 두 사람이 최선을 다해 게임을 플레이 했을 때, (ScoreA - ScoreB) 값을 구하여 출력한다.
제한
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100,000
- 0 ≤ A[i], B[i] ≤ 100,000
풀이
두 사람이 최선을 다해 각자의 목표를 최대화 했을 때 (ScoreA - ScoreB) 값이 무엇인지 구해야 한다.
Alice가 최선을 다한다는 것은 ScoreA는 최대로, ScoreB는 최소로 하는 선택을 하는 것이다.
그러면 Alice는 상자를 선택했을 때 차이가 큰 상자를 우선적으로 선택해야 한다.
여기서 차이는 다른 상자와 차이를 말한다.
예를 들어
- 상자1: A[1] = 10, B[1] = 5
- 상자2: A[2] = 100, B[2] = 90
- 상자 3: A[3] = 2, B[3] = 0
라고 했을 때
A[1] - B[2] = -80, A[2] - B[1] = 95다.
그러면 상자1보다는 상자2를 선택해야 한다.
그리고 마지막 상자3이랑 비교하면
A[2] - B[3] = 100, A[3] - B[2] = -88이다.
이 경우도 상자3보다는 상자2를 선택하는 것이 맞다.
그렇기 때문에 상자2는 가장 먼저 선택되어야 할 보물 상자다.
그런데 앞에 방식처럼 모든 상자와 비교하며 상자를 선택하는 것은 시간 초과난다. (N <= 10만)
그래서 정렬을 사용해야 한다.
상자1이 상자2보다 우선이고, 상자2가 상자3보다 우선이라면, 당연히 상자1이 상자3보다 우선이다.
이는 정렬이 가능하다는 것을 증명한다. (정렬 조건은 코드에서 확인)
그래서 Alice를 기준으로 정렬을 해주고, Alice, Bob이 정렬된 순서로 상자를 가져가면 각자 목표를 최대화할 수 있다.
Alice를 기준으로 정렬했다고 해도 Bob이 가져가는 상자는 Alice와 동일하다. 왜냐하면 Alice에게 유리한 상자를 가져오는 것은 Bob한테도 유리한 선택이기 때문이다.
시간 복잡도: O(NlogN)
소스 코드
import java.io.*;
import java.util.*;
class Box implements Comparable<Box> {
int A, B, diff;
Box(int A, int B) {
this.A = A;
this.B = B;
this.diff = Math.abs(this.A - this.B);
}
@Override
public int compareTo(Box o) {
int v1 = this.A - o.B;
int v2 = o.A - this.B;
if(v1 > v2) {
return -1;
} else if(v1 < v2) {
return 1;
}
return 0;
}
}
public class Main {
static int T;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int i=0; i<T; i++) {
int N = Integer.parseInt(br.readLine());
Box[] boxs = new Box[N];
for(int j=0; j<N; j++) {
StringTokenizer st = new StringTokenizer(br.readLine());
boxs[j] = new Box(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
Arrays.sort(boxs);
sb.append(answer(boxs)).append("\n");
}
System.out.println(sb.toString().trim());
}
static long answer(Box[] boxs) {
long scoreA = 0;
long scoreB = 0;
boolean turnA = true;
for(int i=0; i<boxs.length; i++) {
if(turnA) {
scoreA += boxs[i].A;
} else {
scoreB += boxs[i].B;
}
turnA = !turnA;
}
return scoreA - scoreB;
}
}