[백준] 조합

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

2407번: 조합

다이나믹 프로그래밍을 이용하는 문제입니다.

 

n,m의 input에 대해 nCm을 계산한 결과를 return하면 됩니다.

 

<Solution>

nCm = n!/(m!*(n-m)!)

이므로, 만약 factorial을 매번 1~특정수 만큼 곱해서 만들면 중복되는 연산들이 존재합니다.

이 과정을 줄이기 위해 factorial dp array를 구성하고, factorial결과를 미리 담아놓고 가져오는 형태로 중복된 계산을 피하도록 구현하면 됩니다.

 

실제 구현은 아래와 같습니다.

import sys

n, m = list(map(int, sys.stdin.readline().rstrip().split()))

def dp_factorial(n):
    dp = [0]*(n+1)
    dp[0] = 1
    for i in range(1,n+1):
        dp[i] = dp[i-1] * i
    return dp

factorial_array = dp_factorial(n)

print(factorial_array[n]//(factorial_array[m]*factorial_array[n-m]))