[BOJ] (G3) 2225. 합분해

👨‍💻 개인 공부 기록용 블로그 입니다.
💡 틀린 내용이나 오타는 댓글, 메일로 제보해주시면 감사하겠습니다!! (__)

링크

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

문제

문제 설명 및 요점

• 0부터 N까지 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구한다.
• 덧셈의 순서가 다르면, 다른 경우로 체크한다.
• 하나의 수를 여러 번 쓸 수 있다.
• 만약 N=3, K=2 라면 (1, 2), (2, 1), (0, 3), (3, 0) 이 정답이 된다.
• 먄약 N=1, K=4 라면 (0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0), (1, 0, 0, 0) 이 정답이 된다.

풀이

#DP

• 특정한 N, K에 대해 문제를 해결하려면, (K - 1) 개의 합에다가 (N - n)을 더하면 된다. (단, n은 N이하의 음이 아닌 정수)
• 위 원리를 가지고 그대로 점화식을 세우면 된다.
• dp[i][j] = j 개의 정수를 합하여 i를 만드는 경우의 수 = sum(dp[0~i][j - 1])
• dp[0][:] 는 모두 1로 잡아둔다. (그래야 그 뒤 값들을 정상적으로 계산할 수 있다. 예를 들어, 1 = 0 + 1 = 1 + 0)
• dp[1][j]는 모두 j이다. (문제 설명을 잘 읽어보고, N=1, K=4인 경우를 다시 생각해보자.)
• dp[:][1] 은 당연히 1이다. (하나의 숫자로 n을 만드는 경우의 수)
• 나머지 값들은 점화식을 통해 채워주면 된다. 단순히 구현하면 시간 복잡도가 $O(N^2K)$ 가 나오는데, 둘 다 200이라서 문제 없이 통과할 수 있다.

코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
dp = [[0] * 201 for _ in range(201)]

for i in range(2):
    for j in range(1, k + 1):
        dp[i][j] = 1 if i == 0 else j

for i in range(n + 1):
    dp[i][1] = 1

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

print(dp[n][k] % 1000000000)