[DP] 백준 2225 파이썬 (합분해) 골드5

-풀이

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):
    dp[i][j] = dp[i-1][j] + dp[i][j-1]
    dp[i][j] %= 1000000000
print(dp[K][N])

-풀이 설명

[30분 no sol] 그리면서까지 규칙을 찾아보려 했지만 찾지 못하였다.  구글링을 해보니 0부터 N까지의 정수를 K개를 이용하여 N을 만드는 방법은 0부터 N개까지 k-1을 만드는 개수의 합과 같다.

 

이를 통해 보았을 때 n=2, k=3 은 (n=0,k=2), (n=1,k=2), (n=2,k=2) 의 합과 같다고 볼 수 있다. 이러한 방식으로 나타내면 O(K*N^2)이지만 풀이 코드와 같이 DP[K][n-1] = DP[K-1][0]+DP[K-1][1]]+…+DP[K-1][n-1] 성질을 이용하여 O(KN) 으로 나타낼 수 있다.

출처 : https://kyun2da.github.io/2020/09/22/sumDecomposition/