[Python 3] BOJ - 16565 "N포커"

 # 문제 링크

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

16565번: N포커

 # 풀이

 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 승리하는 조건은 포카드가 최소 한번 이상 일어나는 것이다. 예를 들어, 현재 뽑아야 하는 카드 갯수가 9개라면, 포카드가 1번 일어나는 경우 혹은 포카드가 2번 일어나는 경우 모두 승리하는 것이다.

 따라서 남은 카드는 절대로 포카드가 되어서는 안된다. 따라서 상태 공간을 현재까지 뽑은 카드수가 cnt, 현재까지 뽑은 카드의 종류(번호 기준)가 kind라고 할 때 포카드가 되지 않는 경우의 수인 dp[cnt][kind]라고 정의한다. 그런데, 현재 cnt개가 있고 다음 카드의 종류를 뽑을 때는 다음 카드를 0장, 1장, 2장, 3장을 고르는 경우가 있다. 그런데, 상태 공간에서 간과한 문양을 생각해야 한다. 왜냐하면 같은 3장을 뽑더라도 문양이 다르면 엄연히 다른 카드이기 때문이다. 따라서 점화식은 다음과 같다. $$ dp[cnt][kind] = \sum_{i = 0}^{3} \  {}_4C{}_i \ * dp[cnt - i][kind - 1] $$ 

 따라서, 현재 뽑아야 하는 카드 수가 n개이고 포카드를 이루는 쌍이 k개라면, 정답에 $ {}_13C{}_K * dp[n-k][13 - k] $ 를 더해주면 된다. 이 때 문제에서 10007로 나눈 나머지를 구해야 하므로 계속 더해주면서 mod연산을 취해주면 정답을 올바르게 구할 수 있다

 

 # 코드

import sys, math

# combination : nCr을 리턴하는 함수
def combination(n, r):
    return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))

# 입력부
n = int(sys.stdin.readline())

# dp : 현재 뽑은 카드수가 cnt개이고 뽑은 카드 종류 수가 kind일 때 포카드가 되지 않는 경우의 수
dp = [[0] * 14 for _ in range(n + 1)]
mod = 10007

# 점화식
dp[0][0] = 1
for i in range(n):
    for j in range(13):
        for k in range(4):
            if i + k <= n:
                dp[i + k][j + 1] += dp[i][j] * combination(4, k)
idx = 1
ans = 0
# 가능한 만큼 포카드의 쌍을 채운다
while 4 * idx <= n:
    temp = combination(13, idx)
    ans += temp * dp[n - 4 * idx][13 - idx]
    ans %= mod
    idx += 1
    
# 정답출력
print(ans % mod)