[백준]1489번 대결

문제 설명

• https://www.acmicpc.net/problem/1489
• Gold 1
• 소요 시간 : 25분

문제 풀이

• 그리디하게 풀이하였다.
• 문제에서 특정 A가 특정 B를 이길 때 가장 근소한 차이로 이겨야만 이후 진행하는 A에 대해서 적은 영향을 줄 수 있다.
• 위 인사이트를 기반으로 우선 A를 오름차순 정렬, B를 내림차순 정렬하고 A의 각 인원별로 B를 순회하여 이기는 사람 중 가장 큰 능력치를 가진사람을 선택하여 승점을 올리고 각 원소를 0으로 만든다.
• 위 순회 이후에 동일 배열을 대상으로 값이 0인 원소 제외 동일한 능력치를 가진 사람이 있는지를 확인하여 무승부 승점을 올리고 동일하게 원소를 0으로 만든다.
• 위 2과정 이후 승점이 결과가 된다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static Integer[] A, B;

    static void solve() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        A = new Integer[N];
        B = new Integer[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            A[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            B[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(A);
        Arrays.sort(B, Collections.reverseOrder());

        // 이기는 경우 결과 갱신
        int result = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (B[j] == 0) continue;
                if (A[i] > B[j]) {
                    result += 2;
                    A[i] = 0;
                    B[j] = 0;
                    break;
                }
            }
        }

        //비기는 경우 결과 갱신
        for (int i = 0; i < N; i++) {
            if (A[i] == 0) continue;
            for (int j = 0; j < N; j++) {
                if (B[j] == 0) continue;
                if (Objects.equals(A[i], B[j])) {
                    result += 1;
                    B[j] = 0;
                    break;
                }
            }
        }
        bw.write(result + "\n");
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        solve();
    }
}

/**
 * 대결 (18:01)
 *
 * - N : 인원수 (N <= 50)
 * - 두 팀의 능력치가 주어졌을 때, 팀 A가 얻을 수 있는 점수의 최대값
 *
 * - 완전 탐색 -> 50!
 * - A를 오름 차순, B를 내림 차순으로 정렬
 * - A를 순회하며 이길수 있는 B중 가장 큰 B를 선택하여 승점 획득
 * - 다시 A를 순회하며 비길 수 있는 B가 있는지 선택하여 무승부 승점 획득
 *
 * N
 * a1 .. an
 * b1 .. bn
 */