예제: 출전 순서 정하기
전세계 최대의 프로그래밍 대회 알고스팟 컵의 결승전이 이틀 앞으로 다가왔습니다. 각 팀은 n명씩의 프로 코더들로 구성되어 있으며, 결승전에서는 각 선수가 한 번씩 출전해 1:1 경기를 벌여 더 많은 승리를 가져가는 팀이 최종적으로 우승하게 됩니다. 각 팀의 감독은 대회 전날, 주최측에 각 선수를 출전시킬 순서를 알려 주어야 합니다.
결승전 이틀 전, 한국팀의 유감독은 첩보를 통해 상대 러시아팀의 출전 순서를 알아냈습니다. 이 대회에서는 각 선수의 실력을 레이팅(rating)으로 표현합니다. 문제를 간단히 하기 위해 1:1 승부에서는 항상 레이팅이 더 높은 선수가 승리하고, 레이팅이 같을 경우 우리 선수가 승리한다고 가정합시다.
표와 같이 출전 순서를 정했다고 하면 한국팀은 2번, 3번, 5번, 6번 경기에서 승리해 전체 네 경기를 이기게 됩니다. 그러나 대신 4번 경기와 1번 경기에 나갈 선수를 바꾸면 1번 경기만을 제외하고 모든 경기에 승리할 수 있지요. 상대방 팀 선수들의 순서를 알고 있을 때, 어느 순서대로 선수들을 내보내야 승수를 최대화할 수 있을까요?입력
입력의 첫 줄에는 테스트 케이스의 수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 각 팀 선수의 수 N(1≤N≤100)가 주어집니다. 그 다음 줄에는 N개의 정수로 러시아팀 각 선수의 레이팅이 출전 순서대로 주어지며, 그 다음 줄에는 N개의 정수로 한국팀 각 선수의 레이팅이 무순으로 주어집니다. 모든 레이팅은 1 이상 4000 이하의 정수입니다.출력
각 테스트 케이스마다 한 줄에 한국팀이 얻을 수 있는 최대 승수를 출력합니다.예제 입력
3 6 3000 2700 2800 2200 2500 1900 2800 2750 2995 1800 2600 2000 3 1 2 3 3 2 1 4 2 3 4 5 1 2 3 4예제 출력
5 3 3
풀이
지난 번 오일러 서킷 문제로부터 받은 상처를 아물게 해주는 아주 고마운 문제였다.
탐욕법을 쓰는 문제로, 필자는 한국의 레이팅을 정렬한 후 이중for문을 돌며 해당 상태에서 최적의 답을 찾는 방법을 사용하였다.
전체적인 소스코드는 아래와 같다.
소스 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<int> korean, russian;
int matchOrder() {
sort(korean.begin(), korean.end());
int res = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (korean[j] >= russian[i]) {
res++;
korean[j] = 0;
break;
}
}
}
return res;
}
int main() {
int testCase;
cin >> testCase;
for (int tc = 0; tc < testCase; tc++) {
cin >> N;
//init
korean = russian = vector<int>(N);
for (int i = 0; i < N; i++) {
cin >> russian[i];
}
for (int i = 0; i < N; i++) {
cin >> korean[i];
}
cout << matchOrder() << endl;
}
return 0;
}풀이 후기
아주 풀기 수월했다 했는데, 역시 도서 풀이에서는 이진 트리를 사용하여 아주 멋드러지게 풀었다. 다행히 C++에서는 set을 제공하지만, 그래도 알아야 쓰지! STL 별표 또 별표!
