[백준] 2407번 > 조합

www.acmicpc.net/problem/2407

2407번: 조합

문제

nCm을 출력한다.

입력

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

출력

nCm을 출력한다.

예제 입력 1

100 6

예제 출력 1

1192052400

 

 

---

풀이

math 라이브러리의 factorial 함수를 import하여 그냥 식을 구현했다.

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

 

해당 문제는 dp로 분류되어 있어서 다른 풀이를 찾아보았다.

n, m = map(int,input().split())
n = int(n)
m = int(m)

dp = [[0]*101 for i in range(101)]

for i in range(n + 1):
    for j in range(i + 1):
        if j == 0:
            dp[i][j] = 1;
        elif j == i:
            dp[i][j] = 1;
        else:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

print(dp[n][m])

• nC0은 무조건 1
• nCn은 무조건 1
• nCm = (n-1)C(m-1) + (n-1)Cm 이라는 점화식을 통하여 dp로 문제해결