[python] 백준 16565 N 포커

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

 

 

문제 해결

• DP를 이용해 n개중 m개를 뽑았는데 그중 k개 종류가 나올 경우의 수를 dp[m][k]라고 정의한다.
  • dp[0][0]은 1로 정의
  • 그러면 $ dp[i][j] = \sum_{k=0}^{3}  \binom{4}{k}  \times dp[i-k][j-1]$ 
• 이후 포카드가 나올 수 있는 경우의 수를 계산하기 위해
  • idx (포카드 나오는 개수)
  • $ ans += \binom{13}{idx} * dp[n-4*idx][13-idx]$

 

CODE

import sys
input = sys.stdin.readline
import math
mod = 10007

def combination(n, r):
    return math.factorial(n)//(math.factorial(r)*math.factorial(n-r))

if __name__ == "__main__":
    n = int(input())
    dp = [[0 for _ in range(14)] for _ in range(n+1)]

    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)