[백준] 2225. 합분해(Python, 파이썬)

백준 온라인의 문제 풀이입니다.

📖 [백준] 2225. 합분해

시간 제한	메모리 제한	난이도
2초	128 MB	골드 5

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

✔️ 입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

✔️ 출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

✔️ 입력 출력 예시

입력	출력
20 2	21
6 4	84

🗒️ 내 풀이

‘1,000,000,000으로 나눈 나머지를 출력한다 라는 문구로’ 다이나믹 프로그래밍을 통해 풀어야겠다고 접근했다. 근데 아무리 생각해도 점화식이 떠오르지 않아서 구글링을 통해 풀었다.

첫번째, 일단 대부분은 2차원 배열에다가 결과 값을 나열해서 규칙을 찾아 푸는 방식을 택했다. 결과 표는 아래와 같다.

	n=1	n=2	n=3	n=4	n=5	$\cdots$
k=1	1	1	1	1	1	$\cdots$
k=2	2	3	4	5	6	$\cdots$
k=3	3	6	10	15	21	$\cdots$

표에서 확인할 수 있듯이 점화식은 dp[n][k] = dp[n][k - 1] + d[n - 1][k] 이 된다.

두번째, 표로 나열해보지 않고 점화식을 도출해보고 싶어서 찾아봤다. 만약 n = 10, k = 3 이면,
10을 5개로 나눈 것 = [0 + (10을 4개로 나눈 것)] + [1 + (9를 4개로 나눈 것)] + $\cdots$ + [9 + (1을 4개로 나눈 것)] + [10 + (0을 4개로 나눈 것)] 이 된다.

즉, dp[n][k] = dp[0][k - 1] + dp[1][k - 1] + $\cdots$ + dp[n - 1][k - 1] + dp[n][k - 1]이 된다.

여기서, dp[n - 1][k] = dp[0][k - 1] + dp[1][k - 1] + $\cdots$ dp[n - 1][k - 1]이 된다.

이 부분은 직관적으로 이해가 안가서 직접 값을 나열해 보고 알게되었다. 이것도 말로 풀어보면
9를 5개로 나눈 것 = [(0을 4개로 나눈 것) + 9] + [(1을 4개로 나눈 것) + 8] + $\cdots$ + [(8을 4개로 나눈 것) + 1] + [(9를 4개로 나눈 것) + 0] 이 된다.

따라서 점화식은 dp[n][k] = dp[n][k - 1] + d[n - 1][k] 이 된다.

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

dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 1

# dp[n][k] = dp[n][k - 1] + dp[n - 1][k]
for i in range(n + 1):
    for j in range(1, k + 1):
        dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD

print(dp[n][k])

💡 TIL

점화식이 잘 안떠오를 땐, 직접 나열해보는 것도 좋은 방법이다!