[알고스팟] 출전 순서 정하기 (탐욕법 레시피)

링크: https://algospot.com/judge/problem/read/MATCHORDER

algospot.com :: MATCHORDER

---

동적 계획법은 시간적으로 효율적이지만, 공간적으로는 그렇지 않을 수 있습니다. 모든 경로를 재귀호출하여 탐색하고 그 결과를 캐싱하기 때문이죠. 만약 공간적으로 효율적인 알고리즘을 작성해야 하는 경우엔 탐욕법을 생각해볼 수 있습니다. 탐욕법은 탐욕법으로 최적해를 찾을 수 있는 문제 또는 동적계획법으로 작성하기엔 메모리 공간을 너무 많이 차지하여 근사해를 구하는 문제에 사용됩니다.

 탐욕법으로 최적해를 찾을 수 있는 문제를 파악하기 위해서는 다음과 같은 두 가지 속성을 고려해야 합니다. 

1. 탐욕적 선택 속성: 현재 부분문제의 탐욕적 선택이 언제나 최적해의 경로에 포함됩니다.
2. 최적 부분 구조: 부분분제의 최적화과 전체해의 최적화로 이어집니다.

일반적으로 두 번째 조건은 직관적으로 파악되기 때문에 첫 번째 조건의 증명에 힘을 쓰게 됩니다.

 위 문제를 풀기 위한 탐욕적 알고리즘은 간단합니다. 러시아 선수들을 하나하나 비교해가며 한국팀에 이길 수 있는 대상이 없는 경우 가장 레이팅이 낮은 선수를 내보내고, 없는 경우엔 상대 선수보다 레이팅이 높은 선수 중 가장 낮은 레이팅의 선수를 내보냅니다.

 이 알고리즘의 탐욕적 정당성은 귀류법으로 증명할 수 있습니다. 우리가 이길 수 없는 경우 가장 높은 레이팅의 선수를 보내서 최적해를 구했다고 가정합시다. 이때 레이팅이 가장 높은 선수는 러시아의 남은 선수 중 한국팀의 레이팅이 가장 낮은 선수가 이길 수 있는 상대는 모두 이길 수 있기 때문에, 레이팅이 가장 높은 선수와 낮은 상대의 출전 순서를 바꾸더라도 최적해에 영향을 미치지 않습니다. 아래 코드는 이를 구현합니다.

 

<파이썬3 소스코드>  

import sys
rl = lambda: sys.stdin.readline()

def max_win():
    kor_idx = 0
    cnt = 0
    for rus_idx in range(len(rus)):
        if rus[rus_idx] <= kor[kor_idx]:
            kor_idx += 1
            cnt += 1
    return cnt

for _ in range(int(rl())):
    N = int(rl())
    rus = list(map(int, rl().split()))
    kor = list(map(int, rl().split()))
    rus.sort(reverse=True)
    kor.sort(reverse=True)
    print(max_win())

 

<C++ 소스코드>

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <set>

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++)
	{
		if (*ratings.rbegin() < russian[rus])
			ratings.erase(ratings.begin());
		else
		{
			ratings.erase(ratings.lower_bound(russian[rus]));
			wins++;
		}
	}
	return wins;
}

vector<int>& inputRatings(vector<int>& vec, const int length)
{
	for (int n = 0; n < length; n++)
	{
		int tmp;
		scanf("%d", &tmp);
		vec.push_back(tmp);
	}
	return vec;
}

int main(void)
{
	int T;
	scanf("%d", &T);
	for (int t = 0; t < T; t++)
	{
		int N;
		vector<int> russian, korean;
		scanf("%d", &N);
		russian = inputRatings(russian, N);
		korean = inputRatings(korean, N);
		
		int result = order(russian, korean);
		printf("%d\n", result);
	}
	return 0;
}