DynamicProgramming1_11조합(2407)

문제

nCm을 출력한다.

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

출력

nCm을 출력한다.

풀이

• nCm을 출력하는 조합 문제이다.
• 파스칼의 삼각형을 이용한 DP 알고리즘을 사용해 해결하였다.
  -dp[n][m] ( nCm ) = dp[n-1][m-1] + dp[n-1][m] 으로 점화식을 두고 전체 dp를 구한 후 원하는 답을 출력

코드

import sys
n , m = map(int, sys.stdin.readline().split(" "))
dp = [[0 for i in range(101)] for j in range(101)]
for i in range(1,101):
    dp[i][0] = 1
    dp[i][i] = 1
for i in range(2,101):
    for t in range(1,i):
        dp[i][t] = dp[i-1][t-1] + dp[i-1][t]
print(dp[n][m])

배운 것

점화식
dp[n][m] ( nCm ) = dp[n-1][m-1] + dp[n-1][m]

코멘트

math모듈의 factorial함수를 사용해서 풀이도 가능하다.

import math

n, m = map(int, input().split())
up = math.factorial(n)
down = (math.factorial(n - m)) * (math.factorial(m))
print(up // down)

조합의 공식은 nCm이라고 했을때, n! / (n - m)! * m!이므로 계산하여 출력해준다.