악곱 == 악성곱슬

DP

---

이 문제는 동적 프로그래밍으로 풀 수 있는 문제이다. 그러나 동적 프로그래밍으로 풀어야 하는지 감이 안올 수 있다. 그런 경우 모든 경우의 수를 생각해보자

N이 100 K가 3 이라고 가정할 때 위와 같은 그림을 그려볼 수 있다.

3 개의 수를 더해서 100을 만들어야 하니, 0 + 0 + 100, 0 + 0 + 99 … 쭉 생각해나갈 수 있다. 이것을 트리 구조로 표현하면 위 그림과 같다. 이를 일반화 하기 위해 f(N, K)라고 하고, N을 조금 다시 고쳐서 생각해보면 0~N까지 고를 수 있는 숫자라고 볼 수 있고, K는 루트를 제외한 트리의 높이로 볼 수 있다.

여기서 트리를 그리고 나면 많은 중복 문제를 발견할 수 있는데, 이를 보고 메모이제이션으로 중복 문제를 제거하여 시간복잡도를 줄일 수 있겠다는 생각을 하며 문제의 유형을 다이나믹 프로그래밍으로 고려해볼 수 있다.

따라서 일반화된 점화식은 f(N, K) = sum( {i=0~N} f(i, K)) 으로 도출할 수 있다. 코드는 다음과 같다.

구현

---

import sys

def dp(n, k):
    table = [[0]*(n+1) for _ in range(k+1)]
    for i in range(n+1):
        table[1][i] = 1

    for height in range(2, k+1):
        for i in range(n+1):
            table[height][i] = (sum(table[height-1][:i+1]) % INF)

    return table[k][n]

if __name__ == "__main__":
    N, K = map(int, sys.stdin.readline().rstrip().split())
    INF = int(1e9)
    print(dp(N, K))