백준 16565번, N포커

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

16565번: N포커

 

요약

 

트럼프 카드를 이용하여 새로운 규칙의 게임을 만든다. 52장의 카드 중 N장을 선택했을 때, 이 중 포카드 (four of a kind)를 만들 수 있다면 플레이어의 승리이다. 포카드는 "같은 숫자를 가진, 다른 문양의 4장의 카드" 이다. 주어진 N에 대하여 플레이어가 승리하는 경우의 수를 출력한다.

---

1. 하나의 포카드 쌍은 4개의 카드를 포함한다. 따라서, $N$개의 카드를 선택하였을 때는 최대 $N/4$개의 포카드 쌍을 형성할 수 있다. N개의 카드 중 하나 이상의 포카드 쌍을 형성하면 승리한다. 따라서, 1, 2, 3, ... , $N/4$개의 포카드 쌍을 형성하는 경우의 수를 모두 더한다.

 

2. 단순히 생각했을 때, $i$개의 포카드 쌍을 형성하는 경우의 수는 다음과 같다. $\binom{13}{i}\times \binom{52 - 4i}{N - 4i}$

13개의 숫자 중, $i$개의 숫자 쌍을 선택하고, 남은 $52 - 4\times i$의 카드 중 $N - 4\times i$개의 카드를 택하는 것이다. 그러나, 남은 $52 - 4\times i$의 카드 중 $N - 4\times i$개의 카드를 택하는 과정에서 추가적으로 다른 포카드 쌍이 형성될 수 있다.

 

3.  $i = 1$일 때를 예로 들어, $\binom{13}{1}$으로 숫자 1이 선택되어 포카드 쌍이 형성되었다고 하자. 그리고 $N - 4$개의 카드를 택하는 과정에서 숫자 2를 공통으로 가지는 포카드 쌍 하나가 추가로 형성되었다면, 이는 $\binom{13}{1}$으로 숫자 2가 선택되어 포카드 쌍이 형성되고, $N - 4$개의 카드를 택하는 과정에서 숫자 1을 공통으로 가지는 포카드 쌍 하나가 형성되는 것과 같은 경우의 수이다. 따라서, 처음에 $i$개의 포카드 쌍을 형성하는 것을 고정해놓고 나머지 카드를 고르는 값은 다음과 같다.

 

$\binom{13}{1}\times \binom{52 - 4}{N - 4} = 1 \times four(1) + 2\times four(2) + 3\times four(3) + ... + n/4\times four(n/4)$

 

$\binom{13}{2}\times \binom{52 - 8}{N - 8} = 1 \times four(2) + 3\times four(3) + 4\times four(4) + ... + n/4\times four(n/4)$

 

$\binom{13}{3}\times \binom{52 - 12}{N - 12} = 1 \times four(3) + 4\times four(4) + 5\times four(5) + ... + n/4\times four(n/4)$

 

이때, $four(n)$은 고른 카드 더미에 n개의 포카드 쌍이 포함되어 있다는 의미이다.

 

4. 우리가 구하고자 하는 값은 
$four(1) + four(2) + four(3) +... four(n/4)$ 이므로, $i$가 홀수일 때의 값은 더해주고, 짝수일 때의 값은 빼줌으로써 정답을 구할 수 있다.

 

5. 풀이에서 파스칼의 삼각형을 이용, DP로 조합을 전처리하여 사용하면 시간복잡도는 $O(N^2)$이고, 이후에 값에 접근하는 것은 $O(1)$에 가능하다. 답을 구할 때는 시간복잡도 $O(N)$으로 문제를 해결할 수 있다.

#include <iostream>
using namespace std;

const int mod = 10007;

int N, ans;
int combination[53][53];

int comb(int N, int K);

int main(void) {
	cin >> N;	
	for (int i = 1; i <= N / 4; i++) {
		if (i % 2 == 1) {
			ans += (comb(13, i) * comb(52 - i * 4, N - i * 4)) % mod;
			ans = ans % mod;
		}
		else {
			ans -= (comb(13, i) * comb(52 - i * 4, N - i * 4)) % mod;
			ans = (ans + mod) % mod; // modular계에서 뺄셈을 진행할 때에는 음수가 되는 경우를 고려하여 mod를 더해준다.
		}
	}
	cout << ans;		
	return 0;
}

int comb(int N, int K) {
	if (combination[N][K] != 0) return combination[N][K];
	else if (K == 0 || K == N) combination[N][K] = 1;
	else combination[N][K] = (comb(N - 1, K - 1) + comb(N - 1, K)) % mod;
	return combination[N][K];
}