[백준2225] 합분해

문제

---

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

2225번: 합분해

 

생각의 흐름

---

dp를 이용해 d[i][j]에는 i개를 더해 j가 되는 경우의 수를 저장한다. 그런데 생각을 해보면 d[i][j]=d[i][j-1]+d[i-1][j]라는 걸 알 수 있다. dp를 직접 표로 그려 계산해보면 이해가 좀 더 쉬울 것이다.

 

코드

---

# 백준 2225

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

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

print(dp[k][n])