[알고리즘/동적 계획법] 2407번 : 조합 - python

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

2407번: 조합

 

---

• 문제
• 소요시간: 6분 30초

---

• 설계하기(접근방법) 

1. n과 m을 입력받는다

2. 동적 계획법으로 풀어보자

 

dp를 n+1개 만큼 생성한 후

 

팩토리얼을 생성하기 위해서

dp[n] = dp[n-1] * n 을 반복해준다

 

3. 조합식 형식에 맞추어 출력해준다

 

 

---

• 코드(출력)

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

dp = [0] * (n + 1)

dp[0] = 1
dp[1] = 1

for i in range(2, n + 1):
    dp[i] = i * dp[i - 1]

comb = dp[n] // (dp[n-m] * dp[m])

print(comb)

---

• 얻어갈 부분

1. 동적 계획법으로 풀 경우 일반적인 팩토리얼보다 느리긴 했지만 재사용성이 뛰어나다.