[알고 스팟] 출전 순서 정하기 - 탐욕법

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 

 

출전 순서 정하기(링크)

탐욕적으로 해결할 수 있을까?

매번 승부에서 탐욕적인 선택들을 시도해보자. 먼저 항상 가장 실력이 좋은 선수를 출전시킨다. 이 경우 2 번 이긴다.

 

러시아팀    3,000    2,700    2,800    2,200    2,500    1,900

한국팀       2,995    2,800    2,750    2,600    2,000    1,800

 

약간의 직관을 이용해 좀 더 개선해보자. 많은 게임에서 이겨야 하는데 실력 좋은 선수를 모두 먼저 내보내면 후반부에 레이팅이 높은 상대가 나오는 경우 속수무책이다.

 

따라서, 매번 게임에서 가장 근소한 차이로 이길만한 선수를 내보내자. 약한 상대를 만나는 경우에 우리팀의 강한 선수를 굳이 낭비하지 않을 기회를 얻을 수 있다. 이 경우 3 번 이긴다.

 

러시아팀    3,000    2,700    2,800    2,200    2,500    1,900

한국팀       2,995    2,750    2,800    2,600    2,000    1,800

 

이기는 횟수가 늘었지만 아직 아쉬운 부분이 있다. 첫 번째 게임에 출전하는 러시아 선수를 이길 우리 선수는 없다. 즉, 어떻게 해도 지는 게임이지만 가장 근소한 차이의 선수를 내보냄으로써 가장 강한 선수를 낭비한다.

 

이를 개선하기 위해 가장 근소한 차이로 이기는 선수를 선택하되 어차피 이길 수 없는 선수를 만난다면 가장 약한 선수를 출전시키자. 이 경우 5 번 이긴다.

 

러시아팀    3,000    2,700    2,800    2,200    2,500    1,900

한국팀        1,800    2,750    2,800    2,600    2,995    2,000

 

대부분의 게임을 이기는 마지막 방법을 우리가 선택할 방법으로 가정하고 이 방법의 정당성을 증명해보자.

탐욕적 방법의 정당성 증명

먼저, 이 문제가 최적 부분 구조를 가지는지 생각해보자. 직관적으로 모든 경기에서 최대한 이기는 것이 좋다. 즉, 각 부분 문제(각 경기)의 최적해(이기는 선택)는 전체 문제의 최적해(최다 승)가 된다.

 

최적 부분 구조를 가지기 때문에 각 경기에서의 탐욕적 선택이 최적해라는 것을 증명하면 탐욕적인 방법으로 전체 문제의 최적해를 구할 수 있다. 그렇다면 문제가 탐욕적 선택 속성을 가지는지 증명하자. 전체적인 흐름은 이전 포스팅에서 소개한 증명 방법과 같다.

 

게임에서 이기는 경우 우리의 탐욕적 선택은 '가장 근소한 차이로 이기는 선수를 출전 시키는 것' 이고, 게임에서 지는 경우 탐욕적 선택은 '가장 낮은 레이팅의 선수를 출전 시키는 것' 이다. 두 경우를 나누어 증명해보자.

 

상대를 이기는 경우에 가장 근소한 차이로 이기는 선수가 아닌 그 다음 레이팅의 선수를 출전시키는 최적해가 있다고 하자. 다음 레이팅의 선수가 아니라 가장 근소하게 이기는 선수로 바꿔 출전 시키면 손해일까?

 

가장 근소하게 이기는 선수로 바꿔도 어차피 이기는 게임이다. 그리고 더 높은 레이팅의 선수가 이후 경기 중 하나에 참여하므로 전체 승수는 (늘면 늘었지) 줄어들지 않는다. 즉, 우리의 탐욕적 선택인 '가장 근소하게 이기는 선수의 출전' 은 손해가 없다.

 

상대에게 지는 경우에 가장 낮은 레이팅이 아닌 그 다음 번 레이팅의 선수를 출전시킨 최적해가 있다고 하자. 이를 가장 낮은 레이팅의 선수로 바꿔 출전 시키면 손해일까? 

 

가장 낮은 레이팅의 선수로 바꾸나 마나 어차피 지는 게임이다. 그런데 가장 약한 선수로 바꿈으로써 더 좋은 선수가 이후의 경기 중 하나에 참여하므로 전체 승수는 (늘면 늘었지) 줄어들지 않는다. 즉, 우리의 탐욕적 선택인 '가장 약한 선수의 출전' 은 손해가 없다.

C++ 코드

#include <bits/stdc++.h>

using namespace std;

int order(const vector<int>& russian, const vector<int>& korean) {
    int n = russian.size(), wins = 0;
    multiset<int> ratings(korean.begin(), korean.end());
    for (int rus = 0; rus < n; ++rus) {
        // rbegin() points the highest element.
        if (*ratings.rbegin() < russian[rus])
            // Use the lowest rating since you can't win anyway.
            ratings.erase(ratings.begin());
        else {
            // Use the lowest rating among those who can win.
            ratings.erase(ratings.lower_bound(russian[rus]));
            ++wins;
        }
    }
    return wins;
}

int main() {
    vector<int> russian = {3000,2700,2800,2200,2500,1900};
    vector<int> korean = {2800,2750,29950,1800,2600,2000};

    cout << "Maximum wins: " << order(russian, korean) << '\n';

    return 0;
}