백준 16471: 작은 수 내기

문제 요약

보드게임에 자신이 있는 주언이는 사장님에게 게임 룰을 물어보았고, 그 룰은 다음과 같았다.

1. 각자 N장의 카드를 받는다. (N은 홀수다)
2. 각자 카드를 1장씩 골라서 카드에 적힌 수의 크기를 비교한다. (각 카드에 적힌 수는 0이상, 100,000이하의 정수다)
3. 더 작은 수가 적힌 카드를 낸 사람이 1점을 얻고, 승부에 사용된 카드는 버린다. (무승부의 경우, 둘 다 점수를 획득하지 못한다)
4. 총 N번의 승부 후, (N+1)/2점 이상의 점수를 획득한 사람이 승리한다.
5. (N+1)/2점 이상의 점수를 획득한 사람이 없을 경우, 승자가 없는 것으로 게임이 끝난다.
주언이는 자신이 이길 확률이 조금이라도 있을 경우 게임을 하고자 한다.

사장님이 받은 카드에 적힌 수들과, 주언이가 받은 카드에 적힌 수들이 주어질 때, 주언이가 게임을 해도 되는지 확인하자.

문제 분류

• 그리디 알고리즘
• 정렬

문제 풀이

결국 사장님보다 작은 수를 내야하지만, 그 중에서도 가장 큰 수를 내는 것이 목적이다. 사장님이 4의 카드를 냈을 때에도 1이 아닌 3을 내야 한다.

자신이 받은 카드에 숫자 k가 적혀있을 경우, k인덱스를 1 증가시키는 것으로 카드카운팅을 한다. 그리고 결국 사장님이 갖고 있는 카드보다 작으면서도 가장 큰 숫자를 하나씩 지워나가며, 그렇게 지워나간 갯수가 (n + 1) / 2이상이 된다면 YES, 아니면 NO이다.

풀이 코드

#include <stdio.h>
#include <iostream>

using namespace std;

int ary[100001];
int ary2[100000];

int main() {
	int n, in, cnt = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d", &in);
		ary[in]++;
	}
	for (int i = 0; i < n; i++)
		scanf("%d", ary2 + i);	

	for (int i = 0; i < n; i++) {
		for (int j = ary2[i] - 1; j >= 0; j--) {
			if (ary[j] > 0) {
				ary[j]--;
				cnt++;
				break;
			}
		}
		if (cnt >= (n + 1) / 2) {
			printf("YES");
			return 0;
		}
	}	
	printf("NO");
	return 0;
}