[PS] N포커 / C++ (백준 16565번)

 

조합론의 포함 배제의 원리를 사용하여 포카드가 나올 경우의 수를 구하는 문제

dp[N][K] = N장의 카드를 뽑을 때, K개의 포카드 세트가 나올 수 있는 경우의 수를 저장하는 형식으로 1~N까지 차례로 구하며 dp로 풀 수 있을 것 같아서 5시간 동안 점화식을 찾았다...

 

결론적으로 이 전의 경우의 수는 관계 X

N개의 카드를 뽑을 때, K개의 포카드 세트가 나왔다고 고정한 뒤, 나올 수 있는 경우의 수를 구한다.

식: $cmp = {_{13}C_K} + {_{(52 - k \times 4)}C_{(N - K \times 4)}}$

K를 1~N/4까지 구해준 다음, 포함 배제의 원리에 의해서 홀수번째는 더해주고, 짝수번째는 빼주면 N개의 카드를 뽑을 때 포카드가 나올 경우의 수를 구할 수 있다.

 

ex) N이 17일 때

Ans = 포카드 1세트를 고정한 경우의 수 - 포카드 2세트를 고정한 경우의 수 + 포카드 3세트를 고정한 경우의 수 - 포카드 4세트를 고정한 경우의 수

$ = ({_{13}C_1} + {_{48}C_{13}}) - \left( {_{13}C_2} + {_{44}C_9} \right) + \left( {_{13}C_3} + {_{40}C_5} \right) - \left( {_{13}C_4} + {_{36}C_1} \right)$ 가 된다.

 

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

long long com[53][53];

long long combination(int n, int r)
{
	if (n == r || r == 0)
		return 1;
	if (com[n][r])return com[n][r];
	com[n][r] = (combination(n - 1, r - 1) + combination(n - 1, r)) % 10007;
	return com[n][r];
}

int main()
{
	int n;
	long long ans = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n/4; i++) {
		long long cmp = (combination(13, i) * combination(52 - i * 4, n - i * 4)) % 10007;
		if (i % 2 == 1)
			ans += cmp;
		else ans = ans - cmp + 10007;
		ans %= 10007;
	}
	
	printf("%lld\n", ans);
	
	return 0;
}