High Card Wins

알고리즘 구분 : 그리디

문제

Bessie the cow is a huge fan of card games, which is quite surprising, given her lack of opposable thumbs. Unfortunately, none of the other cows in the herd are good opponents. They are so bad, in fact, that they always play in a completely predictable fashion! Nonetheless, it can still be a challenge for Bessie to figure out how to win.

Bessie and her friend Elsie are currently playing a simple card game where they take a deck of 2N cards, conveniently numbered 1 ... 2N, and divide them into N cards for Bessie and N cards for Elsie. The two then play N rounds, where in each round Bessie and Elsie both play a single card, and the player with the highest card earns a point.

Given that Bessie can predict the order in which Elsie will play her cards, please determine the maximum number of points Bessie can win.

입력
The first line of input contains the value of N (1 <= N <= 50,000).
The next N lines contain the cards that Elsie will play in each of the successive rounds of the game. Note that it is easy to determine Bessie's cards from this information.

출력
Output a single line giving the maximum number of points Bessie can score.

예제 입력 1
3
1
6
4
예제 출력 1
2

문제 풀이

문제를 해석하자면, 입력받는 값이 N(1 <= N <= 50000)일 때, 카드는 총 1 ~ 2N까지의 숫자가 적힌 카드가 존재한다. 그 중 N장은 Bessie가 가져가고, 나머지 N장은 Elsie가 가져간다.
게임은 총 N라운드를 진행하며, 입력에서 Elsie가 N라운드 동안 내게 될 카드가 무엇인지 주어진다. 이러한 상황에서, Bessie가 총 몇 라운드를 이길 수 있는지를 파악하는 문제이다.

처음 생각한 방법은 card vector를 생성한 뒤, Elsie나 내게 될 카드에 대해서는 1로 표기하고, 나머지 카드에는 2로 표기하여 Bessie가 가지게 될 카드로 표시한다.
예제를 기준으로 한다면,
index : 1 2 3 4 5 6
player : 1 2 2 1 2 1 (1 == Elsie, 2 == Bessie)
위와 같이 표현이 될 것이다.
해당 상태에서 elsie가 가지고 있는 카드를 시작점으로 잡아 이보다 큰 카드를 가지고 있는지 확인하는 반복문을 돌려 확인하는 과정을 반복하도록 구현하였다.
그러나 시간복잡도를 계산해보았을 때, 전체 카드를 순회하게 되므로 최대 O(N^2)의 시간복잡도를 가지게 되기에, 해당 풀이는 TLE를 받게 되었다.

TLE 소스 코드

#include <bits/stdc++.h>

using namespace std;

int n;
struct node {
	int player = 0;
	bool use = false;
};
vector<node> card(100001); // first는 player, second는 사용여부
vector<int> elsie;
void solve();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for(int i = 0; i < n; i++) {
		int input;
		cin >> input;
		card[input].player = 1;
		elsie.push_back(input);
	}
	
	solve();
	
	return 0;
}

void solve() {
	int result = 0;
	
	sort(elsie.begin(), elsie.end(), less<int>());
		
	for(int i = 0; i < elsie.size(); i++) {
		int now = elsie[i];
		for(int j = now + 1; j < (2 * n) + 1; j++) {
			if(card[j].player == 0 && card[j].use == false) {
				result++;
				card[j].use = true;
				break;
			}
		}
	}

	cout << result << endl;
}

위의 코드는 완전 탐색 수준이기에, Elsie와 Bessie의 보유 카드 vector를 별도로 만들어 이 둘의 카드끼리만 비교하는 방식으로 구현했다. 이렇게 구현한다면, Elsie의 vector size와 Bessie의 vector size는 동일하게 N이며, Elsie의 vector하나에서 게임을 이길 수 있는 경우의 수를 찾기 위에 Bessie의 vector를 순회하게 되나, 여기서 Bessie vector의 순회시작점을 계속 변경해주기에, 실제 시간복잡도는 O(N^2)보다 작게 되어 시간 초과가 발생하지 않는다.

• sort 정렬 기준을 직접 만드는 연습은 조금 더 해야할 것 같다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

int n;
struct inform {
	int num = 987654321;
	bool use = false;
};
vector<inform> elsie;
vector<inform> bessie;
bool compare(const inform& i1, const inform& i2); //정렬 함수
void solve();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for(int i = 0; i < n; i++) {
		inform input;
		cin >> input.num;
		elsie.push_back(input);
	}
	
	solve();
	
	return 0;
}

bool compare(const inform& i1, const inform& i2) {
	if(i1.num < i2.num) return true;

	return false;
}


void solve() {
	int idx = 0;
	int result = 0;
	
	sort(elsie.begin(), elsie.end(), compare);
	
	for(int i = 1; i < (2 * n) + 1; i++) {
		if(elsie[idx].num != i) {
			inform input;
			input.num = i;
			bessie.push_back(input);
		}
		else {
			idx++;
		}
	}
	
	idx = 0;
	for(int i = 0; i < elsie.size(); i++) {
		for(int j = idx; j < bessie.size(); j++) {
			if(elsie[i].num < bessie[j].num && bessie[j].use == false) {
				result++;
				idx++;
				bessie[j].use = true;
				break;
			}
		}
	}
	
	cout << result << endl;
}

• 문제 출처 : https://www.acmicpc.net/problem/11968
• 해당 풀이는 백준에서 "맞았습니다!!"판정을 받았습니다.