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

문제 링크

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

algospot.com :: MATCHORDER

 

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

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

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

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

 

 

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

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

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

 

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

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

 

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

 

 

구현 코드