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

문제 링크

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

algospot.com :: MATCHORDER

 

상대방을 이길 수 있는 한국선수가 있다면 그 중 레이팅이 가장 낮은 선수를 선택해야 합니다.

무조건 상대방보다 레이팅이 높다고 해당 선수를 배치하게되면 이후에 레이팅이 낮은 선수들만 남아 경기에 질 확률이 더 크기 때문입니다.

마찬가지로 상대선수를 이길 수 있는 한국선수가 없다면 선수 중 가장 낮은 선수를 선택해야 합니다.

우리 팀에서 가장 높은 레이팅으로도 이길 수 없다면 가장 레이팅이 낮은 선수를 사용해 레이팅이 높은 선수를 아껴둘 수 있기 때문입니다.

 

 

이 방식을 위 예시에 적용해보면

가장먼저 한국선수 중 레이팅이 가장 높은 선수와 첫 번째 러시아 선수와 비교해봅니다.

해당 러시아 선수가 한국에서 가장 레이팅이 높은 선수보다 레이팅이 높기 때문에 한국에서 가장 레이팅이 낮은 점수인 18과 30을 매칭시킵니다.

 

다음 러시아 선수와 가장 레이팅이 높은 한국선수를 비교했을 때 한국선수가 더 높기 때문에

해당 러시아 선수와 이길 수 있는 가장 낮은 점수인 27을 매칭시켜줍니다.

 

이러한 방식으로 모든 러시아 선수를 비교해 나가면  최대 승수를 구할 수 있습니다.

 

 

구현 코드

 

	#include <iostream>
	#include <set>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
	using namespace std;
	int russian[100];
	int korean[100];
	int n;
	int order(){
	int wins = 0;
	//한국 선수를 오름차순으로 정렬시킨다.
	multiset<int> ratings(korean, korean+n);
	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;
	}
	int main(){
	fastio;
	int _;
	cin >> _;
	while(_--){
	cin >> n;
	for(int i=0;i<n;i++)
	cin >> russian[i];
	for(int i=0;i<n;i++)
	cin >> korean[i];
	cout << order() << endl;
	}
	return 0;
	}

view raw matchorder.cpp hosted with ❤ by GitHub