bj16565 N포커

문제

• 백준 URL: N포커
• 난이도 골드 2

풀이

mod = 10007

MAXN = 52
C = [[0]*(MAXN+1) for _ in range(MAXN+1)]
for i in range(MAXN+1):
    C[i][0] = 1
    for j in range(1,i+1):
        C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod

import sys
N = int(sys.stdin.readline().strip())

ans = 0
maxk = min(13,N//4)
for k in range(1,maxk+1):
    r = 52 - 4*k
    n = N - 4*k
    n1 = C[13][k]
    n2 = C[r][n] if 0 <= n <= r else 0
    term = (n1 * n2) % mod

    ans = ((ans + term) if (k%2)==1 else (ans - term)) % mod

print(ans % mod)

'적어도 하나'라는 조건이 붙는 경우의 수 문제는 '포함-배제의 원리(Principle of Inclusion-Exclusion)'를 사용하여 푸는 것이 정석이다.

직접 '포카드가 하나만 있을 때', '두 개 있을 때', ... 등을 계산하는 것은 매우 복잡하다. 대신 다음과 같은 논리를 사용한다.

1. (포카드가 1종류 이상 있는 모든 경우의 수)를 더한다
   • 여기에는 포카드가 2종류, 3종류 있는 경우가 중복으로 계산된다
2. (포카드가 2종류 이상 있는 모든 경우의 수)를 뺀다
   • 이제 2종류 있는 경우는 제대로 한 번만 계산되었지만, 3종류 있는 경우는 너무 많이 빼서 문제가 된다.
3. (포카드가 3종류 이상 있는 모든 경우의 수)를 다시 더한다
4. 이 과정을 계속 반복한다. 즉, 홀수 종류의 포카드를 갖는 경우는 더하고, 짝수 종류의 포카드를 갖는 경우는 뺀다.

mod = 10007

MAXN = 52
C = [[0]*(MAXN+1) for _ in range(MAXN+1)]
for i in range(MAXN+1):
    C[i][0] = 1
    for j in range(1,i+1):
        C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod

가장 먼저 조합(nCr) 값을 미리 계산하여 저장하는 2차원 배열을 만든다. C[n][r]은 nCr의 값을 가진다. 파스칼의 삼각형 원리(nCr = n-1Cr-1 + n-1Cr)를 이용해 DP 방식으로 효율적으로 계산한다.

import sys
N = int(sys.stdin.readline().strip())

ans = 0
maxk = min(13,N//4)
for k in range(1,maxk+1):

k는 포카드의 종류 개수이다. k개의 포카드를 만들려면 최소 4*k장의 카드가 필요하므로 k는 N//4를 넘을 수 없다. 또한, 숫자 종류는 총 13개이므로 13을 넘을 수도 없다. 따라서 k의 최댓값은 min(13, N//4)가 된다.
그리고 포함-배제의 원리를 적용하기 위해 k=1부터 maxk까지 순회한다.

    r = 52 - 4*k
    n = N - 4*k
    n1 = C[13][k]
    n2 = C[r][n] if 0 <= n <= r else 0
    term = (n1 * n2) % mod

    ans = ((ans + term) if (k%2)==1 else (ans - term)) % mod

n1은 13가지 숫자 종류 중 k개를 선택하는 경우의 수이다.
n2는 k종류의 포카드(4×k장)를 제외한 나머지 카드 중에서 N장을 채우기 위해 더 필요한 카드를 뽑는 경우의 수이다.

그리고 포함-배제 원리를 이용해 k가 홀수이면 term을 더하고, k가 짝수이면 term을 빼서 최종 결과 ans를 계산한다.