[Python] 백준 2225번 : 합분해

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

2225번: 합분해

---

💡 문제 풀이

DP 문제이다. 항상 절차대로 접근하면 된다.

 

DP에는 i개의 숫자로 숫자 n을 만드는 경우의 수를 저장한다.

DP[0]에는 0부터 숫자를 사용할 수 있으므로 몇 개의 숫자를 쓰던 경우의 수는 1이다.

표를 통해서 이해해 보자.

2를 2개로 만드는 경우는 (0, 2), (1, 1), (2, 0) 3가지이다.

이 경우는 (0을 한 개만 사용) * (2를 한 개만 사용) + (2를 한 개만 사용) * (0를 한 개만 사용)

+ (1을 한 개만 사용) * (1를 한 개만 사용) 이렇게 3가지로 볼 수 있다.

 

숫자 n을 m개로 만드는 경우를 DP[n][m]라고 할 때, 이 값은 DP[n-1][m-1] + ... DP[0][m-1]의 값과 같다.

DP[n-1][m]은 DP[n-1][m-1] + ... + DP[0][m-1]과 같기 때문에 점화식은 다음과 같다.

✔️ 느낀 점

솔직히 내 스스로 풀 수 없던 문제인 것 같다. 풀기 위해서 오랜 시간을 투자했지만 진짜 말도 안 된다.

다음부터 최대한 표를 세우는 방식을 선택해야겠다. DP는 정말 싫다..

💻 코드

import sys

n, k = map(int, sys.stdin.readline().split())
mod = 1000000000
DP = [0 for _ in range(n+1)]
DP[0] = 1

for _ in range(1, k+1):
    for i in range(1, n+1):
        DP[i] = (DP[i] + DP[i-1]) % mod
        
print(DP[n])