반응형
https://www.acmicpc.net/problem/16565
16565번: N포커
첫째 줄에 N장의 카드를 뽑았을 때, 플레이어가 이기는 경우의 수를 10,007로 나눈 나머지를 출력하라.
www.acmicpc.net
[ 문제풀이 ]
이 문제에서는 포함 배제의 원리를 활용해 문제를 풀어야 하므로 다음 글을 일고 오시면 좋습니다!
https://rudalsd.tistory.com/47?category=1064608
[ 알고리즘 ] 포함 배제의 원리(Inclusion–exclusion principle)
오늘은 포함 배제의 원리(Inclusion-exclusion principle)에 대해 설명드리겠습니다. 유한한 집합의 합집합의 총 원소의 개수를 세는 방법입니다. [ 동작 원리 ] 즉, 겹치는 집합의 개수가 홀수이면 해당
rudalsd.tistory.com
먼저 모든 조합의 개수를 dp를 이용하여 구해줍니다. iCj = i-1Cj-1 + i-1Cj라는 점화식을 이용하여 구해주면 쉽게 구할 수 있습니다.
comb [ i ][ j ] = comb [ i - 1 ][ j - 1 ] + comb [ i - 1 ][ j ];
이를 통해서 포카드가 1개 이상일 때, 2개 이상일 때, 3개 이상일 때 ··· 13개 이상일 때의 조합의 개수를 각각 더해주거나 빼주면서 답을 구하면 됩니다.
포함 배제의 원리를 이용하여 포카드의 개수가 홀수일 때는 더해주고, 짝수일 때는 빼주면 답을 구할 수 있습니다.
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include <iostream> #define MOD 10007 using namespace std; int comb[53][53]; int N; int main() { for (int i = 0; i < 53; i++) { //iCj의 조합을 dp를 활용해서 미리 구해 놓음 for (int j = 0; j <= i; j++) { if (i == j || j == 0) { comb[i][j] = 1; } else if (j == 1) { comb[i][j] = i; } else { comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD; } } } cin >> N; int ans = 0; for (int i = 1; i <= N / 4; i++) { //포함 배제의 원리 if (i % 2 == 1) { //포카드 조합이 홀수일 때 ans += (comb[13][i] * comb[52 - 4 * i][N - 4 * i]) % MOD; } else { //포카드 조합이 짝수일 때 ans -= (comb[13][i] * comb[52 - 4 * i][N - 4 * i]) % MOD; } ans = (ans + MOD) % MOD; } cout << ans; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 1019번 - 책 페이지 (C++) (0) | 2022.07.03 |
|---|---|
| [ 백준 ] 17436번 - 소수의 배수 (C++) (0) | 2022.07.02 |
| [ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++) (0) | 2022.06.30 |
| [ 백준 ] 13334번 - 철로 (C++) (0) | 2022.06.29 |
| [ 백준 ] 14725번 - 개미굴 (C++) (0) | 2022.06.28 |