알고리즘 - Python / 백준 - 2407번 : 조합

2407번: 조합 (acmicpc.net)

2407번: 조합

 

---

풀이

• 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])

---