출전 순서 정하기

풀이

완전 탐색 알고리즘

$n$명의 선수들의 순서를 정하는 방법은 $n!$개 있습니다. $n!$은 숫자가 조금만 커져도 계산량이 매우 많아집니다.

동적 계획법

한국팀의 출전 순서를 맨 앞에서부터 한 명씩 정해가기로 하면, 각 선수를 지금까지 순서에 추가했는지를 나타내는 boolean값 배열만을 받는 부분 문제를 만들 수 있습니다.

$order(taken)$=각 한국팀 선수를 이미 순서에 추가했는지의 여부가 $taken$에 주어질 때, 남은 선수들을 적절히 배치해서 얻을 수 있는 최대 승수

$taken$에 포함된 true의 수를 세면 이번에 선택할 선수가 러시아팀의 어떤 선수와 경기하게 되는지도 알 수 있으니, $taken$ 외에 다른 인자는 필요가 없습니다. 그러면 $O(n\cdot 2^n)$시간의 동적 계획법 알고리즘을 얻을 수 있습니다. 하지만 여전히 $n=100$이라면 제한 시간 내에 해결할 수 없습니다.

탐욕적 알고리즘의 구상

이 문제를 탐욕적으로 해결하는 방법은 여러가지가 있지만 직관적으로 떠오르는 방법이 있습니다. 질 때는 크게 지고 이길 때는 작게 이기는 것입니다.

탐욕적 선택 속성 증명

위 방법의 정당성을 증명하기 위해, 항상 우리가 하는 선택을 포함하는 최적해가 존재함을 증명해야 합니다. 각 경기에 대해 이 경기를 질 수밖에 없는 경우, 그리고 이 경기를 이길 수 있는 경우로 나눠 우리의 선택이 옳다는 것을 보이겠습니다.
먼저 이 경기를 질 수밖에 없는 경우를 고려해 봅시다. 상대팀 선수가 모든 우리 팀 선수보다 레이팅이 높을 경우, 이 경기는 항상 질 수 밖에 없습니다. 이 경기에 가장 레이팅이 낮은 선수 $A$ 대신 선수 $B$를 내보내는 최적해가 있다고 가정합시다. 최적해에서 $A$와 $B$의 순서를 바꾸면 이번 경기는 어차피 질 테지만, $A$를 상대했던 선수 $x$는 레이팅이 더 높은 선수를 상대하게 됩니다. 따라서 승수가 더 줄어들 일은 없고, 이 경기에 $A$를 내보내는 최적해가 존재함을 알게 됩니다.
다음으로는 이 경기를 이길 수 있는 경우를 고려합시다. 상대팀 선수보다 레이팅이 높거나 같은 우리 선수가 있다면 이 경기를 승리할 수 있습니다. 승리할 수 있는 선수 중 레이팅이 가장 낮은 $A$ 대신 레이팅이 더 높은 $B$를 내보내는 최적해가 있다고 가정합시다. 이 최적해에서 $A$와 $B$의 위치를 바꿔 봅시다. 이번 경기는 어차피 승리할 테고, $A$를 상대했던 $x$는 레이팅이 더 높은 선수를 상대하게 됩니다. 따라서 승수가 더 줄어들 일은 없고, 이 경기에 $A$를 내보내는 최적해가 존재함을 알게 됩니다. 반대로 선수 $A$보다 레이팅이 더 낮은 선수를 내보내야할 경우가 있을까요? $A$ 대신 레이팅이 더 낮은 $C$를 내보내는 최적해가 있다고 가정합시다. 그러면 이 경기를 지게 됩니다. 이 최적해에서 $A$와 $C$의 위치를 바꾸면 이 경기는 승리로 바뀝니다. $A$가 했던 경기는 $C$가 대신 해서 질 수도 있겠지만, 승수가 1 늘고 1 줄었으니 결과적으로는 여전히 최적해입니다.
이렇게 두 경우 모두 우리의 선택은 최다승을 보장한다는 사실을 알 수 있습니다.

최적 부분 구조 증명

첫 번째 경기에 나갈 선수를 선택하고 나면 남은 선수들을 경기에 배정하는 부분 문제를 얻을 수 있습니다. 이때 남은 경이에서도 당연히 최다승을 얻는 것이 좋으니 최적 부분 구조도 자명하게 성립함을 알 수 있습니다.

구현

import java.util.*;

public class Main {

    public static int N;
    public static ArrayList<Integer> russian, korean;
    public static int result;

    public static void input(Scanner scanner) {
        N = scanner.nextInt();
        russian = new ArrayList<>();
        korean = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            russian.add(scanner.nextInt());
        }
        for (int i = 0; i < N; i++) {
            korean.add(scanner.nextInt());
        }
    }

    public static void solve() {
        result = order(russian, korean);
    }

    public static int order(ArrayList<Integer> russian, ArrayList<Integer> korean) {
        int wins = 0;
        // 선수들의 순서는 바뀌어도 최다승은 같으므로 정렬함
        Collections.sort(russian);
        Collections.sort(korean);
        // 한국 선수를 기준으로 오름차순 순서대로 비교하면 경기를 질 수 밖에 없는 경우, 경기를 이길 수 있는 경우 둘 다 최적의 선택을 할 수 있다.
        int rus = 0;
        for (int kor = 0; kor < N; kor++) {
            if (russian.get(rus) <= korean.get(kor)) {
                rus++;
                wins++;
            }
        }

        return wins;
    }

    public static void output() {
        System.out.println(result);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

만약 $order()$ 함수를 $treeSet$으로 구현한다면 러시아팀 $n$명의 선수들을 이길 수 있을 때마다 한국팀에서 가장 작게 이기는 선수를 찾기 위해 $O(\log n)$시간이 걸리는 연산을 해야 하므로 전체 시간 복잡도는 $O(n\log n)$입니다. 하지만 양 팀을 레이팅을 기준으로 오름차순으로 정렬한다면 더 빠르게 해결할 수 있습니다.
우리는 한국팀의 선수들만 순서를 바꿔서 최다승을 할 수 있는 순서를 찾으려 했지만 러시아팀의 순서를 바꿔도 우리가 찾으려는 답은 같습니다. 따라서 두 팀 모두 오름차순으로 정렬하고 한국팀 선수를 기준으로 러시아팀 선수와 차례차례 비교하면 최적해를 구할 수 있습니다. 그 과정은 다음과 같습니다.
경기를 질 수 밖에 없는 경우 그냥 넘어가면 kor가 1 증가하므로 가장 레이팅이 낮은 선수가 경기를 하는 것으로 생각할 수 있습니다. 한국팀의 kor번째 선수가 러시아팀의 rus번째 선수를 이길 수 있을 때 rus++하고 wins++ 해도 괜찮은 이유는 그게 가장 작게 이기는 경우이기 때문입니다. kor번째 선수 이전에 더 작게 이길 수 있는 경우가 있다고 가정한다면, 더 작게 이길 수 있는 선수와 경기했던 선수는 더 크게 이길 수 있는 선수와 경기하게 되므로 승수에 영향이 없습니다. 만약 더 작게 이길 수 있는 선수가 질 수 밖에 없어서 넘어간 경우 "kor번째 선수 이전에 더 작게 이길 수 있는 경우가 있다"라는 명제는 모순입니다. 왜냐하면 한국팀 선수들과 러시아팀 선수들은 경기력 순으로 오름차순으로 정렬되어 있기 때문에 러시아팀의 rus번째 선수는 한국팀의 kor번째 선수 이전의 선수는 절대 이길 수 없습니다.

회고