[Python]2225. 합분해

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

2225번: 합분해

---

2차원 DP로 접근하면 쉽게 해결할 수 있는 문제였다.

조건에서 0<=K<=N 이며 여러번 중복해서 사용할 수 있고 순서가 다르면 다른 경우로 친다고 하였다.

K와 N이 어떤 관계인지 도식화해서 알아보자

 

 

K=3 일때 N=2 인 경우를 만들기 위해선 K=2 일때 i=0, 1, 2 의 경우를 모두 참조하고 끝에다가 (N-i) 을 더하는 것을 볼 수 있다.

정리하자면, DP[K][N] = DP[K-1][0] + DP[K-1][1]+ ... + DP[K-1][N] 인 형태이다.

 

코드는 다음과 같다. 복잡도는 K*N^2 이다.

n, k = map(int,input().split())
mod = 1000000000
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 l in range(j+1):
            dp[i][j] += dp[i-1][j-l]
        dp[i][j] %= mod
print(dp[k][n])

 

위 성질을 이용해 복잡도를 KN 까지 낮춰보자

DP[K][N-1] = DP[K-1][0]+DP[K-1][1]]+...+DP[K-1][N-1] 이므로

DP[K][N] = DP[K-1][0]+DP[K-1][1]]+...+DP[K-1][N-1]+DP[K-1][N]

                   = DP[K][N-1]+DP[K-1][N] 

n, k = map(int,input().split())
mod = 1000000000
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] %= mod
print(dp[k][n])