< DP > 2225번 합분해 with 파이썬

 

문제

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

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

입력

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

출력

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

정답비율

41.793%

알고리즘 분류

 #DP #다이나믹프로그래밍

 

n, k = map(int, input().split())
dp = [[1]*(n + 1) for _ in range(k + 1)]
for i in range(1, k+1):
    dp[i][1] = i

for i in range(2, k+1):
    for j in range(2, n+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[k][n] % 1000000000)

 

 - 규칙을 찾긴 했는데 왜 이런 규칙이 되는지 고민을 많이했던 문제이다.

 - 먼저 표를 그렸다.

K ＼ N	1	2	3	4
1	1	1	1	1
2	2	3	4	5
3	3	6	10	15
4	4

 - 각 행을 K로 두고 N을 만들 수 있는 경우의 수를 적어보았다. 그랬더니 위와 같은 표가 나타났고, 바로 윗행의 같은열의 데이터와 같은 행의 바로 이전 데이터의 합이 답임을 알 수 있었다.

 

 - 그러나 왜 이런 결과가 나왔을까에 대해서 고민을 해보았는데, 결과는 다음과 같다.

 

 - 예를 들어 3을 3개의 수를 이용해서 만드려면 총 10개의 경우가 나오는데, 이는 3을 2개의 숫자로 만드는 경우의 가장 앞에 0을 더해주는 경우와, 2를 3개의 숫자로 만드는 경우의 가장 앞에 1을 더해주는 경우의 합이 되는 것이다.

 

 - 몇개만 살펴보면 3을 2개의 숫자로 만드는 경우는 1+2, 3+0 ...이 있는데, 앞에 0을 더해주도록하면 0+1+2, 0+3+0 과 같이 된다. 도한 2를 3개의 숫자로 만드는 경우는 0+1+1, 1+0+1 ...이 있는데, 앞에 1을 더해주도록 하여 위와 겹치지 않는 1+1+1, 2+0+1... 과 같이 3을 만들 수 있게된다. 먼저 수행한 식은 0으로 시작하고 뒤에서 수행한 식은 0으로 시작하지 않기 때문에 절대 겹치지 않는다.

 

 - 이제 dp 점화식으로 나타내면 dp[i][j] = dp[i-1][j] + dp[i][j-1] 이 된다.

 

 

 

 

---

 

 

참고

 

2225번: 합분해