[BaekJoon 2225 : 동적계획법, Python] - 합분해

백준 2225 합분해 : 골드 5

Solution

import sys
input = sys.stdin.readline
n, k = map(int, input().split())

DP = [[0]*(k+1) for _ in range(n+1)]    
for i in range(k+1):
    DP[0][i] = 1

for i in range(1, n+1):
    for j in range(1, k+1):
        DP[i][j] = (DP[i][j-1] + DP[i-1][j])%1000000000

print(DP[n][k])

풀이과정 및 느낀점

점화식을 만들어내는 게 굉장히 까다로웠다.
이걸 좀 작은 n, k 값을 가진 케이스로 일일이 표를 만들어보면 규칙성이 얼추 보이긴 하는데 솔직히 왜 그렇게 되는 건진 알 수가 없었다.
내가 문제를 보자마자 처음에 만든 점화식은
DP[i][j] = DP[i][j-1] + (DP[i-1][j-1] + DP[i-2][j-1] + …. + DP[0][j-1])
위와 같은데, 이걸 코드로 구현하려면 for 문을 3번을 돌려야 해서 (i 에 대한 것, j에 대한 것, i보다 작은 범위에 대해서 1번 더) 코드도 길어지고 시간초과가 날 거 같았다.
근데 생각해보니, 점화식의 괄호쳐진 부분은 사실 DP[i-1][j] 와 같았다. 이렇게 점화식을 만들면 for 문을 두 번만 돌려도 되고, 코드도 훨씬 간결해진다.
케이스별로 테이블을 만들어서 점화식을 도출해내진 못했지만 초기 버전의 점화식의 하부 구조를 간단하게 만들어서 개서된 버전의 점화식을 만들어낼 수 있었다.
시간이 꽤 오래 걸렸고, 어쨌든 완성된 점화식의 유도 과정은 아래와 같다.

합분해 점화식 유도
DP[i][j] = DP[i][j-1] + (DP[i-1][j-1] + DP[i-2][j-1] + …. + DP[0][j-1])
DP[i-1][j-1] + DP[i-2][j-1] + …. + DP[0][j-1] = DP[i-1][j]
DP[i][j] = DP[i][j-1] + DP[i-1][j]