문제 링크
문제
티어: 골드 1
알고리즘: 그리디, 정렬
팀 A와 B가 대결을 하려고 한다. 각 팀에 속한 사람은 다른 팀에 속한 사람과 대결을 해야 한다. 두 팀에 속한 각 사람은 대결을 한 번씩 해야 한다. 대결의 승자는 2점을 획득하고, 무승부인 경우에는 1점을 획득한다.
팀 A에 속한 사람의 능력치는 A1, A2, ..., AN이고, 팀 B에 속한 사람의 능력치는 B1, B2, ..., BN이다. 대결은 능력치가 높은 사람이 이기며, 능력치가 같은 경우 비긴다.
두 팀의 능력치가 주어졌을 때, 팀 A가 얻을 수 있는 점수의 최댓값을 구해보자.
입력
첫째 줄에 팀에 속한 사람의 수 N이 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어지고, 셋째 줄에는 B1, B2, ..., BN이 주어진다.
출력
첫째 줄에 팀 A가 얻을 수 있는 점수의 최댓값을 출력한다.
제한
- 1 ≤ N ≤ 50
- 1 ≤ Ai, Bi ≤ 1,000
풀이
팀 A가 얻을 수 있는 점수의 최댓값을 출력해야 한다.
팀 A가 최대로 이기는 경우를 생각해 보면, 가장 근소한 차이로 이기는 것이 다음 팀원이 이길 수 있는 가능성을 최대로 하기 때문에 최선의 선택이라고 할 수 있다.
그런데 무승부인 경우 무승부를 선택하고, 다음 팀원이 이길 수 있게끔 하는 경우가 최선이 될 수 있지 않을까? 라는 의문이 들었다.
이러한 의문은 간단하게 증명할 수 있다.
5 6 8 9
3 5 4 3
라고 했을 때
5는 비기는 경우와 이기는 경우가 존재한다.
4를 선택하는 경우보다 5를 선택하는 경우 6은 5 대신 4를 이길 수 있다. 그렇지만, 5와 같다는 것은 다음 수인 6보다 작다는 의미이기 때문에 4점 얻을 점수를 3점 얻게 될 것이다.
그렇기 때문에 핵심은 가장 근소한 차이로 이기는 경우를 우선적으로 선택하고, 이후에 비기는 경우를 탐색해서 얻은 점수가 최적의 점수가 된다.
가장 근소한 차이는 A 배열을 오름차순, B 배열을 내림차순해서 A가 B의 큰 요소부터 탐색을 하고, 처음으로 이기는 지점이 가장 근소한 차이로 이기는 지점이 된다. A의 다음 지점은 현재 지점보다 크기 때문이다.
이기는 경우를 구했다면, 비기는 경우를 구하면, 그 값이 최적해가 된다.
Integer 배열이기 때문에 요소를 비교할 때 Objects.equals()를 사용해야 한다는 점을 주의하자. (==는 객체의 주소를 비교함)
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
Integer[] A = new Integer[N];
Integer[] B = new Integer[N];
StringTokenizer stA = new StringTokenizer(br.readLine());
StringTokenizer stB = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
A[i] = Integer.parseInt(stA.nextToken());
B[i] = Integer.parseInt(stB.nextToken());
}
Arrays.sort(A);
Arrays.sort(B, Collections.reverseOrder());
int answer = 0;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(B[j] == -1) {
continue;
}
if(A[i] > B[j]) {
//B[j]가 현재 매칭되어 있지 않다면
//승리하는 것 중 가장 근소한 차이로 승리한 경우를 선택
//매칭 되었다는 의미에서 -1
A[i] = -1;
B[j] = -1;
answer += 2;
break;
}
}
}
for(int i=0; i<N; i++) {
if(A[i] == -1) {
//이미 매칭된 것은 최적으로 매칭되었기 때문에 continue;
continue;
}
for(int j=0; j<N; j++) {
if(B[j] == -1) {
continue;
}
if(Objects.equals(A[i], B[j])) {
//매칭되지 않은 것 중 다음 우선순위인 무승부를 확인함.
B[j] = -1;
answer += 1;
break;
}
}
}
System.out.println(answer);
}
}