[백준][python] 2407.조합 - DP

• 백준 2407 조합 Silver II
• 문제링크

2407번: 조합

나의 접근

nCr을 구하는 문제로, 동적계획법으로 n! / r!(n - r)! 를 계산하면 된다. 팩토리얼을 어떻게 구현하는 것이 관건이다. N번째에 해당하는 factorial을 재귀적으로 계산해나가며 딕셔너리에 key, value로 저장한다.

import sys

N, R = map(int, sys.stdin.readline().split())

def dp(num):
    arr = {}
    if num in arr:
        return arr[num]
    elif num == 0 or num == 1:
        arr[num] = 1
        return 1
    else:
        factorial = num * dp(num - 1)
        arr[num] = factorial
    return factorial

ans = dp(N) // (dp(R) * dp(N - R))
print(ans)