🟩 [백준] [Python] [Gold5] 2225번_합 분해

문제

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

2225번: 합분해

풀이

# 백준 2225번 문제 - 합분해
import sys
input = sys.stdin.readline

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

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

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

DP 문제인데 점화식을 찾는데 너무 오래걸렸다. 

n과 k의 관계에 대해 생각해봐야 한다. 

i \ j	n = 0	n = 1	n = 2	n = 3
k = 0	0	0	0	0
k = 1	1 (0)	1 (1) -> 자기 자신	1	1
k = 2	1 (0,0)	2 (0,1) (1,0)	3	4
k = 3	1	3 (0,0,1) (0,1,0) (1,0,0)	6	10

위의 그래프를 보면 k = 0 일때 합이 n이 되는 수는 찾을 수 없다. 

다음으로 넘어가서 k = 1일 때는 n과 관계없이 n 자신을 선택하는 방법밖에 존재하지 않아 모두 1가지이다.

k = 2 일 때는 n + 1이라는 점화식을 구할 수 있다. 

k = 3 일 때는 dp[ i ] [ j ] = dp[ i - 1 ][ j ] + dp[ i ][ j - 1 ] 이라는 점화식이 성립된다. 

 

표를 그려서 구하면 매우 쉬웠는데 복잡하게 생각할 필요가 없었다.