[백준-2225] 합분해

---

나의 코드

import sys
input = sys.stdin.readline

n,k=map(int,input().split())

dp=[[0]*k for _ in range(n+1)]
dp[1]=[1]*k
for i in range(2,n+1):
    prev=sum(dp[i-1])
    li=[0]*k
    for j in range(k):
        if j==0:
            li[j]=prev
        else:
            li[j]=li[j-1]-dp[i-1][j-1]
    dp[i]=li

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

수행시간: 76ms

---

나의 풀이

k=4일때 n의 값을 1부터 올려보면
1일때는 (0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0)로 총4개이다
2일때는 1일때 경우들에 (0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0)을 각각 더해준 경우로 4+3+2+1=10개이다.
3일때는 2일때 경우들에 (0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0)을 각각 더해준 경우로 10+6+3+1=20 == 10+(10-4)+(10-4-3)+(10-4-3-2)이다.
이를 이용해서 li에 [(0,0,0,1)을 더한개수, (0,0,1,0)을 더한개수, (0,1,0,0)을 더한개수, (1,0,0,0)을 더한 개수]를 넣어 li를 dp에 넣는다.

이 풀이는 내가 생각한 풀이로 다른 사람들의 풀이가 깔끔하다.

---

다른 사람들 코드

n, k = map(int,input().split())
dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(0, n+1):
    for j in range(1, k+1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[n][k] % 1000000000)

풀이

만약 n=20,k=5라면 20을 5개로 나눈것은 [0+(20을4개로 나눈것)]+[1+(19를4개로 나눈것)]+...+[20+(0을 4개로나눈것)] 이다.
이를 점화식으로 나타내면 dp[n][k]=dp[0][k-1]+dp[1][k-1]+...+dp[n][k-1] 이다.
이때 dp[n-1][k]=dp[0][k-1]+dp[1][k-1]+...+dp[n-1][k-1]이므로 dp[n][k]=dp[n-1][k]+dp[n][k-1]이다.