취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11968번 문제인 High Card Wins이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/11968

먼저, 주어진 수들을 읽어 입력으로 주어지지 않은 $N$개의 수가 Bessie가 가진 카드에 적힌 수임을 이용해 두 Bessie와 Elsie가 가진 각 카드의 수를 구하자. 또한 Elsie가 어떤 순서로 카드를 내더라도 그에 대응하는 카드를 맞춰 내면 경기의 결과를 변하지 않게 할 수 있으므로 Elsie의 카드 내는 순서는 중요하지 않음을 관찰하자. 아래에서는 Elsie가 자신이 가진 카드 중 작은 수부터 제출하는 경우를 생각할 것이다.

Elsie가 낸 두 카드 $e_1$와 $e_2$, Bessie가 그에 맞춰서 낸 두 카드 $b_1$, $b_2$에 대하여 $e_1<e_2$, $e_1<b_1$, $e_2<b_2$가 성립한다고 가정해보자. 이 때 $b_1>b_2$가 성립한다면 $e_1<b_2$, $e_2<b_1$ 또한 성립함을 관찰하자. 이를 이용하면 어떤 Elsie의 카드의 집합에 대하여 그에 Bessie가 가진 카드의 같은 크기의 부분집합으로 대응되는 Bessie가 모두 이기는 대응이 존재한다면 그 대응을 $e$와 $b$의 크기순 대응으로도 얻을 수 있음을 알 수 있다.

위에서 알아낸 내용을 이용하면, Elsie의 카드를 작은 값이 적힌 카드부터 살피며 그보다 큰 수 중 가장 작은 수가 적힌 Bessie의 카드를 대응시키는 greedy한 전략으로 Bessie가 얻을 수 있는 최대 점수를 계산할 수 있음을 증명할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using namespace std;

int N;
bool A[100001];
priority_queue<int, vector<int>, greater<>> pq1, pq2;
int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		A[x] = 1;
	}
	for (int i = 1; i <= N * 2; i++) {
		if (A[i]) pq2.push(i);
		else pq1.push(i);
	}
	while (!pq1.empty()) {
		if (pq1.top() > pq2.top()) ans++, pq1.pop(), pq2.pop();
		else pq1.pop();
	}

	cout << ans;
}