[Algospot] 출전 순서 정하기 (문제 ID : MATCHORDER)

문제

전세계 최대의 프로그래밍 대회 알고스팟 컵의 결승전이 이틀 앞으로 다가왔습니다. 각 팀은 n명씩의 프로 코더들로 구성되어 있으며, 결승전에서는 각 선수가 한 번씩 출전해 1:1 경기를 벌여 더 많은 승리를 가져가는 팀이 최종적으로 우승하게 됩니다. 각 팀의 감독은 대회 전날, 주최측에 각 선수를 출전시킬 순서를 알려 주어야 합니다.

결승전 이틀 전, 한국팀의 유감독은 첩보를 통해 상대 러시아팀의 출전 순서를 알아냈습니다. 이 대회에서는 각 선수의 실력을 레이팅(rating)으로 표현합니다. 문제를 간단히 하기 위해 1:1 승부에서는 항상 레이팅이 더 높은 선수가 승리하고, 레이팅이 같을 경우 우리 선수가 승리한다고 가정합시다.

경기123456

러시아팀	3,000	2,700	2,800	2,200	2,500	1,900
한국팀	2,800	2,750	2,995	1,800	2,600	2,000

표와 같이 출전 순서를 정했다고 하면 한국팀은 2번, 3번, 5번, 6번 경기에서 승리해 전체 네 경기를 이기게 됩니다. 그러나 대신 4번 경기와 1번 경기에 나갈 선수를 바꾸면 1번 경기만을 제외하고 모든 경기에 승리할 수 있지요. 상대방 팀 선수들의 순서를 알고 있을 때, 어느 순서대로 선수들을 내보내야 승수를 최대화할 수 있을까요?

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 각 팀 선수의 수 N(1≤N≤100)가 주어집니다. 그 다음 줄에는 N개의 정수로 러시아팀 각 선수의 레이팅이 출전 순서대로 주어지며, 그 다음 줄에는 N개의 정수로 한국팀 각 선수의 레이팅이 무순으로 주어집니다. 모든 레이팅은 1 이상 4000 이하의 정수입니다.

 

출력

각 테스트 케이스마다 한 줄에 한국팀이 얻을 수 있는 최대 승수를 출력합니다.

---

greedy 알고리즘의 첫 문제이다.

러시아와 한국 선수들을 점수에 따라 오름차순으로 정렬한다. 정렬한 후 한국 선수들을 탐색할 인덱스를 따로 설정해 둔 후 러시아의 가장 점수가 낮은 선수보다 점수가 높은 한국 선수중 제일 점수가 낮은 선수를 찾는다. 그 선수를 선택한 후 인덱스를 높이며 모든 선수를 탐색한다. 책에서는 이진검색트리를 사용했는데 이렇게 풀어도 통과된다.

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/MATCHORDER.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int C, N, res;
void order(vector<int> russia, vector<int> korea)
{
	sort(russia.begin(), russia.end());
	sort(korea.begin(), korea.end());
	int idx = 0;
	for (int i = 0; i < N; i++) {
		while (idx < N && russia[i] > korea[idx]) {
			idx++;
		}
		if (idx >= N) break;
		idx++;
		res++;
	}
}
int main()
{
	cin >> C;
	while (C--) {
		cin >> N;
		res = 0;
		vector<int> russia(N);
		vector<int> korea(N);
		for (int i = 0; i < N; i++) cin >> russia[i];
		for (int j = 0; j < N; j++) cin >> korea[j];
		order(russia, korea);
		cout << res << endl;
	}
}