감도 안잡히는 2차원 DP 리스트

#2225번 합분해 https://www.acmicpc.net/problem/2225

2225번: 합분해

 

DP리스트를 2차원으로 구현해야 성공할 수 있는 문제였다.

 

dp의 구조는 dp[K][N] : K개의 수로 N이라는 수를 분해할 경우의 수 로 해석할 수 있다.

dp  내부의 2차원 리스트의 길이는 입력된 수 num이 되어야한다.

 

예를 들어, 10을 3개의 수로 분해하는 경우의 수를 동적 계획법으로 구하는 방법은

 

dp[0] = [0,0,0,0,0,0,0,0,0,0,0] -> 0~10까지의 수를 0개의 수로 분해하는 경우의 수는 각각 0이다.

dp[1] = [1,1,1,1,1,1,1,1,1,1,1] -> 1개의 수로 분해하는 경우의 수는 각각 1이다.

---- 여기까지 초기값 설정 ----

dp[2] = [1,2,3,4,5,6,7,8,9,10,11] -> 2개의 수로 분해하는 경우의 수는 각각 dp[1][:목표수] 의 합이다.

 

그러니까, 0을 2개의 수로 분해하는 경우는 1개 : (0,0)

1을 2개의 수로 분해하는 경우는 2개 : (0,1), (1,0)

2를 2개의 수로 분해하는 경우는 3개 : (0,2), (2,0), (1,1) 

이렇게 순차적으로 증가하는데, dp[1]에서 구해진 수를 목표수 index까지 더해준 값과 같다.

 

이렇게 계획해서 진행하면 된다.

 

그럼 dp[3][10] 에 위치한 값 = 10을 3개의 수로 분해하는 경우의 수가 된다.

 

알면 알수록 신기한 알고리즘의 세계이다..

 

num, N = map(int, input().split())

dp = [[0 for x in range(num+1)], [1 for x in range(num+1)]]

for i in range(2, N+1):
    tmp = [0]*(num+1)
    for j in range(num+1):
        tmp[j] = sum(dp[i-1][:j+1])
    dp.append(tmp)
mod = 1000000000
print(dp[N][num] % mod)