백준(Python) 2225번 합분해 풀이

Python으로 구현한 2225번 합분해 문제 풀이입니다.

 

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

2225번: 합분해

---

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
dp = [[0] * 201 for _ in range(201)]

for i in range(201) :
	dp[1][i] = 1
	dp[2][i] = i + 1

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

print(dp[k][n])

 

1. 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구해보면 아래와 같다.

합분해 경우의 수

2. 특정 수로 N=2 이고 K=3인 경우의 수(6)를 보면 N=1, K=3인 경우의 수(dp[i-1][j] = 3)와 N=2, K=2인 경우의 수

   (dp[i][j-1] = 3)의 합임을 알 수 있다.

 

3. 결론적으로, dp[k][n] = dp[k-1][n] + dp[k][n-1] 이라는 점화식을 도출해낼 수 있다.

 

4. 첫번째 반복문을 통해 dp[1][i] 의 값을 모두 1로 갱신시켜주고, dp[2][i] 의 값을 i + 1로 갱신시켜준다.

 

5. 두번째 반복문과 위 점화식을 통해 연산하고, 1,000,000,000으로 나눈 나머지 값으로 값을 갱신한다.

 

6. 최종적으로 문제에서 요구하는 답(dp[k][n])을 출력한다.