[백준/2225] 합분해 (Python)

Problem : https://www.acmicpc.net/problem/2225

2225번: 합분해

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:06:53

 

---

 

문제 설명

 

 

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

 

출력

 

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

입력 예시

 

20 2

 

출력 예시

 

21

 

 

---

 

풀이

 

DP를 이용해서 풀 수 있는 간단한 문제. DP[i][j]를 0부터 j까지의 정수 i개를 더해서 그 합이 j가 되는 경우의 수라고 가정하자. 이는 재귀적으로, 0 <= k <= j인 k에 대해서 (0부터 임의의 수 k까지의 정수 i-1개를 더해서 합이 k인 경우의 수) 의 합이 된다. 이 모든 경우의 수에 대해, j-k를 더하면 정수 i개로 j를 나타낼 수 있기 때문.

 

따라서 O(KN^2)의 시간복잡도 내에 모든 경우를 구할 수 있고, N, K 모두 최대 200이므로 시간 내에 충분히 풀이 가능하다.

 

풀이 코드

MOD = 10**9
N, K = map(int, input().split())

dp = [[0]*(N+1) for _ in range(K+1)]
dp[0][0] = 1

for i in range(1, K+1) :
  for j in range(N+1) :
    for k in range(j+1) :
      dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD

print(dp[-1][-1])

풀이 완료!