백준 16566번 - 카드 게임

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

16566번: 카드 게임

 

문제

 

카드게임의 규칙은 아래와 같다
1. N개의 서로 다른 빨간색 카드 중 M개를 고른다
2. N개의 서로 다른 파란색 카드 중 빨간색 카드의 번호와 같은 카드 M개를 고른다
3. 철수는 빨간색 카드, 민수는 파란색 카드를 가짐
4. 둘은 각각 카드를 한 장씩 내고 번호가 큰 사람이 이김
이 동작을 k번 실행하며 더 많이 이긴 사람이 승리
+ 한 번 낸 카드는 반드시 버려야 함(중복 불가)

철수는 사기를 칠 수 있다. 
즉 중복을 사용할 수 있고, 뽑지 않았던 번호도 사용 가능하다

민수는 철수가 낼 카드를 알아낼 수 있다.
따라서 민수는 철수가 낼 카드보다 큰 카드가 있다면 그 카드들 중 가장 작은 카드 냄(최선의 선택)

입력 : k번 동안 철수가 낼 카드가 입력으로 주어진다
출력 : 민수가 어떤 카드를 낼지 출력하라

 

 

풀이

 

이 문제를 보자마자 upper_bound를 사용해야 되지 않을까?라는 생각이 떠올랐다.

근데 중요한건 중복 불가, 즉 이미 나온 값을 배열에서 제거해야 한다는 점이었다.

 

Linked-list로 구현한다면 가능하겠지만..

위의 방법은 포기했다. (나중에 찾아보니 disjoint-set을 사용하면 쉽게 할 수 있다던데 확인해 보면 좋을 듯)

 

결국 돌고 돌아 Segment Tree를 사용한 풀이법으로 해결했다.

 

풀이의 핵심은 "각 원소보다 큰 수가 얼마나 있는지는 Prefix Sum으로 표현이 가능하다"였다.

 

이는 카드의 숫자를 Tree의 index로 사용해야 한다.

(처음에는 400만의 제한이 있길래 배열이 선언이 될라나 걱정했는데 되네요^^)

 

예를 들어 5보다 크거나 같은 수를 찾으려면 Prefix_Sum [6] - Prefix_Sum [5]~ Prefix_Sum [n]-Prefix_Sum [n-1]까지 돌아보면서 찾으면 된다.

 

그럼 여기서 드는 생각이 6 ~ n까지 돌아본다면 결국 브루트포스 아닌가?라는 생각이 들 수 있다.

맞다. 위 풀이과정은 브루트포스이고 시간 복잡도가 O(n)이기 때문에 아무리 세그 트리를 사용해도 시간 초과가 난다.

 

이럴 때 사용하는 알고리즘이 바로 이분 탐색이다.

요즘은 브루트포스같은 문제가 있으면 이분 탐색이 가능한 지부터 생각해보는 것 같다.

 

어쨌든 이분 탐색으로 O(logn) 시간에 주어진 수보다 크면서 가장 작은 수를 찾아낼 수 있다.

 

(참고로 구현에는 BIT를 사용했다.)

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, k, x;
int tree[4000007];

int sum(int i) {
	int ans = 0;
	while (i > 0) {
		ans += tree[i];
		i -= (i & -i);
	}
	return ans;
}

void update(int i, int num) {
	while (i <= n) {
		tree[i] += num;
		i += (i & -i);
	}
}

int main() {
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		cin >> x;
		update(x, 1);
	}
	for (int i = 0; i < k; i++) {
		cin >> x;
		int l = x, r = n;
		int ans = INT_MAX;
		while (l <= r) {
			int mid = (l + r) / 2;
			int sm = sum(mid), sx = sum(x);
			if (sm - sx > 0) {
				if (mid < ans) ans = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		cout << ans << "\n";
		update(ans, -1);
	}
}