algospot :: MATCHORDER 출전 순서 정하기

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

알고리즘 문제 해결 전략 p. 371

책을 참고하지 않고 코드를 작성함

[알고리즘 STEP. 1]

러시아 선수들을 실력이 낮은 순에서 높은 순으로 정렬한 후에, 우리의 선수들로 이길 수 있는 가장 실력이 높은 순서까지만 이기면 된다.

일단 문제에서 주어진 선수들의 실력을 정렬하자.

러시아	1900	2200	2500	2700	2800	3000
한국	1800	2000	2600	2750	2800	2995

한국의 1800선수로는 1900선수를 이길 수 없다. 1800 선수는 아무도 이길 수 없으므로 제일 잘하는 사람이랑 붙어서 지든 말든 상관이 없다.

그럼 일단 러시아 1900 선수는 한국 2000선수와 매칭시켜서 이기도록 하자

그 다음 러시아 2200 선수는 2600선수로,

2500 선수는 2750 선수로

2700 선수는 2800 선수로

2800 선수는 2995 선수로 이긴다면, 우리는 총 4경기를 이길 수 있다.

이런 식으로, 지금 가진 선수 중 다음번 러시아 선수를 이길 수 있으면서 실력이 가장 안좋은 선수를 붙게 하면, 최대한으로 이길 수 있다.

*int play(int r, int k)

선수들이 실력순으로 나열되어 있을 때, 가장 못하는 러시아 선수 (russia[r])을 이길 수 있는 한국선수를 찾는다.

이길 수 있다면 승리횟수에 1을 더해서 반환하고, 러시아 선수와 한국 선수는 그 다음으로 잘하는 선수들을 다시 비교하게 된다.

    if(korea[k]>= russia[r])
        return 1+play(r+1, k+1);
    else
        return play(r, k+1);

순서가 뒤죽박죽 되는건 나중에 러시아 선수에 맞춰 한국 선수들을 재 정렬하면 되니깐 상관 없다. 

어차피 문제에서 요구하지도 않고 있다. 그냥 이긴 횟수만 구하면 된다.

[최종 코드]

#include <iostream> #include <algorithm> #define FOR(var, ed) for(int var = 0; var<ed; var++) using namespace std; //input int tc, n; int russia[100], korea[100]; int play(int r, int k){ if(r==n || k==n) return 0; if(korea[k]>= russia[r]) return 1+play(r+1, k+1); else return play(r, k+1); } int main(){ // freopen("input.txt", "r", stdin); cin >> tc; while(tc--){ cin >> n; FOR(i, n) cin >> russia[i]; FOR(i, n) cin >> korea[i]; sort(russia, russia+n); sort(korea, korea+n); cout << play(0,0) << endl; } }