백준/16565번/N포커/골드2

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

문제 설명

Site: Baekjoon
Number: 16565
Category: Dynamic Programming, Inclusion-Exclusion Principle
Rank: Gold 2

52장의 카드 중 N개 만큼의 카드를 뽑았을 때, 포카드를 포함하는 총 경우의 수를 구하는 문제입니다.

문제 풀이

처음에 nCr을 통해 문제를 해결하려 지속적으로 생각해보았지만, N이 8보다 크거나 같아지는 순간부터 중복 처리에 관한 문제가 발생하였습니다.

중복되는 경우를 처리하기 위해 포함 배제 원칙 알고리즘을 알 수 있었으며, 이를 통해 다음과 같은 방법으로 해결할 수 있습니다.

존재하는 포카드의 쌍은 총 13개, 포함 배제에 따라 1개의 포카드 쌍을 사용하는 경우는 더하고, 2개는 빼고, 3개는 더하는 방식을 진행하여 주어진 N만큼 진행합니다.

4의 배수인 i에 따라 포카드 쌍을 고르는 경우의 수는 13C(n/4), 52장에서 포카드 쌍에 포함되지 않은 나머지를 계산하는 방법은 (52-i)C(N-i)입니다.

이를 ans값에 더하거나 빼어 정답을 도출하며, 마이너스 값이 나오는 경우를 고려해 마지막에 MOD값을 더하고 다시 % MOD를 통해 정답을 출력합니다.

nCr의 계산

추가적으로 nCr값을 미리 저장하고 진행한다면 연산량을 줄일 수 있기 때문에, nCr = n-1Cr + n-1Cr-1을 통해서 미리 계산합니다.

#include <iostream>

using namespace std;

long long MOD = 10007;

int nCr[53][53];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N;
    cin >> N;

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

    int ans = 0;

    for(int i = 4; i <= N; i += 4)
    {
	    if((i / 4) % 2 == 1)
	    {
            ans += nCr[13][i / 4] * nCr[52 - i][N - i];
	    }
        else
        {
            ans -= nCr[13][i / 4] * nCr[52 - i][N - i];
        }
        ans %= MOD;
    }

    ans = (ans + MOD) % MOD;

    cout << ans;

    return 0;
}