[c언어/c++] 출전 순서 정하기 ( MATCHORDER ) - 탐욕법 ( 그리디, 욕심쟁이 )

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

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

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

#include<stdio.h>

#include<algorithm>

#include<memory.h>

int c;

int n;

int rus[110];

int kor[110];

using namespace std;

int order();

int main(){

scanf("%d",&c);

while(c-- > 0){

scanf("%d",&n);

for(int i = 0 ; i < n ; i++)

scanf(" %d",&rus[i]);

for(int i = 0 ; i < n ; i++)

scanf(" %d",&kor[i]);

sort(kor,kor+n);

sort(rus,rus+n);

reverse(kor,kor+n);

reverse(rus,rus+n);

//for(int i = 0 ; i < n ; i++) printf("%d ", kor[i]);

printf("%d\n",order());

}

return 0;

}

int order(){

int start = 0; int end = n;

int ret = 0;

for(int k = start ; k < n ; k++){

if(start >= end) break;

if( kor[start] < rus[k]){

end--;

}

else{

ret++;

start++;

}

}

return ret;

}