[백준/BOJ] 16565번 : N포커 (DP, 조합론, 포함과 배제의 원리)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 16565번 : 'N포커' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Gold I에 해당하며, 문제를 풀이하기 위해 동적 프로그래밍(DP), 조합론, 포함과 배제의 원리에 대한 이해가 필요합니다.

 

 

16565번 : N포커

 

52장의 트럼프 카드에서 N장을 뽑았을 때 나올 수 있는 포카드 조합의 수를 구하는 문제입니다.

단순한 확률과 통계의 경우의 수 문제임을 알 수 있고, Combination을 어떻게 계산할 수 있을지만 생각해보면 쉽게 해결할 수 있습니다.

 

 

 

그래서 풀이를 깔끔하게 정리해보면, 위와 같이 됩니다.

포카드를 뽑는 경우의 수는 포카드를 1세트 이상 뽑는 경우의 수 - 2세트 이상 뽑는 경우의 수 + ... 이런 식으로 중복되는 경우의 수를 빼고 더해주어서 구해줄 수 있습니다.

이는 포함과 배제의 원리에 의한 것으로, 벤다이어그램에서 겹치는 부분을 빼고 더하는 것을 생각하거나, 집합에서 중복 원소를 빼고 더하는 경우의 수를 생각해보면 간단히 이해할 수 있습니다.

 

그리고 조합의 경우에는 포카드로 뽑을 카드 종류를 선택할 수 있는 경우의 수에 남는 카드 중 아무거나 선택하는 경우의 수를 곱해주면 됩니다.

 

 

#include <bits/stdc++.h>
#define MOD 10007
using namespace std;

int comb[53][53] = {};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    for(int i=0; i<=52; i++) comb[i][0] = 1;
    for(int i=1; i<=52; i++)
        for(int j=1; j<=52; j++)
            comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;

    int N, ans = 0; cin >> N;
    for(int i=1; i<=13 && N-4*i>=0; i++) {
        if(i%2 == 1) ans = (ans + comb[52-4*i][N-4*i]*comb[13][i]) % MOD;
        else ans = (ans - (comb[52-4*i][N-4*i]*comb[13][i]) % MOD + MOD) % MOD;
    }
    cout << ans;
}

 

그래서 위의 풀이를 코드로 작성하면 위와 같이 작성해볼 수 있습니다.

풀이에서 중요한 것을 빼먹었는데, Combination을 연산할 때 시간을 줄이기 위해 i C j = i-1 C j + i-1 C j-1이라는 성질을 활용하여 DP로 빠른 시간에 Combination을 구해줄 수 있습니다.

 

나머지는 풀이에서 작성한 식 그대로 계산해주면 되며, Modulo 계산에서 음수가 나올 수 있으므로 해당 부분을 깔끔히 처리해주어야 합니다.

마이너스 연산을 하는 부분에서 MOD를 한 번 더해주고 Mod 연산을 해주면 음수가 나오지 않도록 방지할 수 있습니다.

 

 

 

풀이 코드를 제출해보면 위와 같은 기록으로 모든 테스트케이스를 통과할 수 있습니다.