[C++] 백준 11968번: High Card Wins

문제 링크

11968번: High Card Wins

문제 요약

베시와 엘시가 1부터 2N까지의 카드를 N개씩 나눠가진다. 둘이 카드를 하나씩 내서 수가 큰 쪽이 이기는 게임을 하려고 한다. 베시는 엘시가 낼 카드의 순서를 알고 있다. 이때 베시는 최대 몇번 승리가 가능한지 구해야 한다.

접근 방법

그리디하게 접근하였습니다.

먼저 엘시가 내는 카드를 입력받고, 그에 속하지 않은 카드를 베시에게 저장하였습니다. 베시와 엘시가 가진 카드들은 모두 오름차순으로 벡터에 저장하였습니다.
각 카드 덱의 처음부터 비교해서 엘시의 카드가 베시의 카드보다 크거나 같으면 베시의 카드의 인덱스를 증가시킵니다. 그 외의 경우에는 승리 횟수를 증가시키고, 베시와 엘시 모두의 카드 인덱스를 증가시킵니다. 만약 베시 또는 엘시의 카드의 인덱스가 끝에 도달한다면 반복을 중단하게 됩니다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX 100001

using namespace std;

bool visited[MAX];

int main(void)
{
	FASTIO;

	int n;
	cin >> n;

	vector<int> v1, v2;
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		v1.push_back(num);
		visited[num] = true;
	}

	sort(ALL(v1));

	for (int i = 1; i <= 2 * n; i++)
		if (!visited[i])
			v2.push_back(i);

	int idx1 = 0, idx2 = 0, res = 0;
	while (1)
	{
		if (v1[idx1] >= v2[idx2])
			idx2++;
		else
			res++, idx1++, idx2++;

		if (idx1 == n || idx2 == n)
			break;
	}

	cout << res << endl;
	return 0;
}