[백준] 2225번 : 합분해

2225번: 합분해

해당 문제는 다이나믹 프로그래밍 문제로 해결하였습니다.

N이 5이고 K가 3일때 구하는 아래의 그림과 같이 표현하였습니다.

첫번째는 모두 한가지 이고,

두번째 부터는 숫자 N일때 이전에 있던 0부터 N까지의 경우의 수를 모두 더한 값과 같다.

예를들어 두번째에 3의 숫자의 경우의 수를 구한다고 한다면

1. 0+3 → 1
2. 1+2 → 1
3. 2+1 → 1
4. 3+0 → 1

총 4가지가 된다. 즉 이전에 있던 경우의수를 0부터 N까지 모두 더한값과 같다.

위의 내용을 코드로 정리하면 아래와 같다.

N , K = map(int, input().split())

dp = [[1 for _ in range(N+1) ] for _ in range(K)]

for i in range(1, K):
    for j in range(len(dp[i])):
        dp[i][j] = 0
        for k in range(j+1):
            dp[i][j] += dp[i-1][k]
            
        dp[i][j] = dp[i][j] % 1000000000
            
print(dp[K-1][N] % 1000000000)