[Python] 백준 2225 합분해

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

2225번: 합분해

 

문제 해결

- 숫자 n을 k개의 숫자로 나타내는 개수를 어떻게 구할 것인가?

- 숫자에 0을 포함한다는 것은 것을 주의하자.

- 잘 모르겠으면 숫자 1 부터 귀납적으로 한 번 해보자!

- 1을 1개 숫자로 1 = 1 (1개), 1을 2개 숫자로 1= 1 + 0 = 0 + 1 (2개) 1 = 1 + 0 + 0 = 0 + 1 + 0 = 0 + 0 + 1 (3개)...

- 2=2 (1개) 2= 2+0 = 1+1 = 0 +2 (3개) ...

표로 정리를 하면

k \ n	n = 1	n=2	n=3
k = 1 (모든 값이1)	1	1	1
k = 2 (모든 값이 n의 값 +1)	2	3	4
k = 3	3	6	10

대충 봤을 때 dp[k][n] = dp[k-1][n] + dp[k][n-1] 이라고 느낄 것이다. 과연 맞을까?

정답은 맞다

dp[k-1][n]= n을 k-1개의 숫자로 나타내는 개수

               =  n을 k-1개의 숫자로 나타내는 개수*1

               = (n을 k-1개의 숫자로 나타내는 개수)*(0을 1개의 숫자로 나타내는 갯수)

               = dp[k-1][n]*dp[1][0]

 

dp[k][n-1] = n-1을 k개의 숫자로 나타내는 개수

                = (n-1을 k-1개의 숫자로 나타내는 개수)*(0을 1개의 숫자로 나타내는 개수)

                  + (n-2을 k-1개의 숫자로 나타내는 개수)*(1을 1개의 숫자로 나타내는 개수) 

                   +(n-3을 k-1개의 숫자로 나타내는 개수)*(2를 1개의 숫자로 나타내는 개수)

                   .......

               = dp[k-1][n-1] + dp[k-1][n-2] ................. + dp[k-1][1] + dp[k-1][0]

 

$dp[k-1][n] + dp[k][n-1] = \sum_{i=0}^n dp[k-i][n]$

 

dp[k][n] = n을 k개의 숫자로 나타내는 개수

            = (n을 k-1개의 숫자로 나타내는 개수)*(0을 1개의 숫자로 나타내는 개수)

             + (n-1을 k-1개의 숫자로 나타내는 개수)*(1을 1개의 숫자로 나타내는 개수)

             + .........

            = dp[k-1][n] + dp[k-1][n-1] + dp[k-1][n-2] ................. + dp[k-1][1] + dp[k-1][0]

            = $\sum_{i=0}^n dp[k-i][n]$

            = dp[k-1][n] + dp[k][n-1]

 

CODE

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
dp = [[0 for _ in range(201)] for _ in range(201)]

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