[백준 C++] 16565번: N포커

1. 문제

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

 

2. 알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 조합론
• 포함 배제의 원리

 

3. 소스 코드

#include <iostream>
#define MOD 10007

using namespace std;

int N;
int Combination[53][53];

// 조합 계산 함수
int cal_combination(int n, int r) {
	
	if (Combination[n][r]) return Combination[n][r];	// 이전에 계산해놓은 값이 있으면, 바로 반환
	else if (n == r || r == 0) Combination[n][r] = 1;	// n=r 이거나, r = 0일 때, 1 반환
	else {
		Combination[n][r] = cal_combination(n - 1, r) + cal_combination(n - 1, r - 1) % MOD;	// nCr = n-1Cr + n-1Cr -1
	}

	return Combination[n][r];
}

int main() {
	// IO 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int ret = 0;

	// N : 카드의 수 입력
	cin >> N;

	/* DP 점화식
	* 4  : 13C1 * 48C0
	* 5  : 13C1 * 48C1
	* 6  : 13C1 * 48C2
	* 7  : 13C1 * 48C3
	* 8  : 13C1 * 48C4 - 13C2 * 44C0
	* 9  : 13C1 * 48C5 - 13C2 * 44C1
	* 10 : 13C1 * 48C6 - 13C2 * 44C2
	* 11 : 13C1 * 48C7 - 13C2 * 44C3
	* 12 : 13C1 * 48C8 - 13C2 * 44C4 + 13C3 * 44C0
	* 13 : 13C1 * 48C9 - 13C2 * 44C5 + 13C3 * 44C1
	*/
	for (int i = 1; i <= N / 4; i++) {
		if (i % 2 == 1) {
			ret += (cal_combination(13, i) * cal_combination(52 - 4 * i, N - 4 * i)) % MOD;
			ret = ret % MOD;
		}
		else {
			ret -= (cal_combination(13, i) * cal_combination(52 - 4 * i, N - 4 * i)) % MOD;
			ret = (ret + MOD) % MOD;
		}
	}

	// 경우의 수 출력
	cout << ret;

	return 0;
}

 

4. 유용한 알고리즘

1) 파스칼 삼각형 + 조합을 통한 조합 계산 방법

int Combination[53][53];

// 조합 계산 함수
int cal_combination(int n, int r) {
	
	if (Combination[n][r]) return Combination[n][r];	// 이전에 계산해놓은 값이 있으면, 바로 반환
	else if (n == r || r == 0) Combination[n][r] = 1;	// n=r 이거나, r = 0일 때, 1 반환
	else {
		Combination[n][r] = cal_combination(n - 1, r) + cal_combination(n - 1, r - 1) % MOD;	// nCr = n-1Cr + n-1Cr -1
	}

	return Combination[n][r];
}