백준 2225번: 합분해

DP만 한참 풀다보니 지치는 것 같아서 기초적인 그래프 문제들도 같이 풀고 있는데
DP문제들 정리가 끝나는 대로 그래프 문제들도 포스팅해야겠다.

문제 : 백준 2225번
알고리즘 : DynamicProgramming

N을 K개의 음이 아닌 정수들의 합으로 표현할 수 있는 경우의 수를 구하는 문제이고
나는 이것을 DP[N][K]으로 표현하였다.

점화식은 다음과 같다.

DP[N][K] =
        DP[0][s] x DP[N][K - s] +
        DP[1][s] x DP[N - 1][K - s] +
        DP[2][s] x DP[N - 2][K - s] +
                    . . .
        DP[N][s] x DP[0][K - s]

s : 0보다 크고 K보다 작은 정수, 즉 조건안에서 아무 숫자든지 상관없다.

예를 들면, N, K = 4, 3 인 경우
DP[4][3] =
         DP[0][1] x DP[4][2] +
         DP[1][1] x DP[3][2] +
         DP[2][1] x DP[2][2] +
         DP[3][1] x DP[1][2] +
         DP[4][1] x DP[0][2]
       = 1 x 5 + 1 x 4 + 1 x 3 + 1 x 2 + 1 x 1
       = 15

import sys
input = sys.stdin.readline
N,K = map(int,input().split())

DP = [[0 for j in range(K + 1)] for i in range(N + 1)]

for n in range(N + 1):
    DP[n][0] = 0 
    DP[n][1] = 1 

for i in range(N + 1) :
    for k in range(2,K + 1):
        for n in range(i + 1):
            DP[i][k] += DP[i - n][1] * DP[n][k - 1]
  
print(DP[N][K] % 1000000000)

s = 1로 하여도 시간초과가 발생하지는 않지만
s 가 K // 2에 최대한 근접했을 때, 시간복잡도를 최소로 할 수 있다.
하지만 DP스럽게 하나씩 차근차근 접근하는 것으로 마무리지었다.

종합 평가

소요시간 : 30분전후
실패 횟수 : 1 , 원인 : 인덱스 범위 오류