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

 

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

 

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

16565번: N포커

---

 

해결전략

 

수학

조합 (Combination)

포함 배제의 원리(Inclusion-Exclusion Principle)

• 여러 개의 집합이 있을 때, 전체 집합의 크기를 구하는 방법.
• 각각의 집합의 크기를 더하고 그 중에서 겹치는 부분을 빼는 방식.

---

 

정답 코드

 

#include <iostream>
using namespace std;

int n;
int com[53][53]; // 조합의 결과를 저장
const int mod = 10007;

int Combination(int N, int K) 
{
	if (com[N][K] != 0) { // 만약 이미 계산된 조합의 결과가 있다면 그 값을 반환
		return com[N][K];
	}
	else if (K == 0 || K == N) {
		com[N][K] = 1;
	}
	else {
		com[N][K] = (Combination(N - 1, K - 1) + Combination(N - 1, K)) % mod;
	}

	return com[N][K];
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;

	int answer = 0;
	for (int i = 1; i <= n / 4; i++) {
		if (i % 2 == 1) {
			answer += (Combination(13, i) * Combination(52 - i*4, n - i*4)) % mod;
			answer = answer % mod;
		}
		else {
			answer -= (Combination(13, i) * Combination(52 - i*4, n - i*4)) % mod;
			answer = (answer + mod) % mod; // 위의 뺄셈 계산에서 answer이 음수가 되는 경우를 고려하여 mod를 더한 후 %mod.
		}
	}

	cout << answer;

	return 0;
}

 

각 집합의 크기

• Combination(13, i) * Combination(52 - i*4, n - i*4)) % mod로 계산
  
  • i가 홀수일 때, 겹치지 않는 부분을 더하고 (i개 집합의 합)
  • i가 짝수일 때, 겹치는 부분을 빼서 (i개 집합의 교집합)
  • 이와 같이 더하고 빼서 전체 집합의 크기를 계산한다.

 

 

---