[백준][Python][2225][DP] 합분해

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

2225번: 합분해

DP 문제다. 

배열의 의미는 다음과 같다 

• 세로 K = K개의 숫자를 쓴다
• 가로 N = 0-n 까지를 써서 만든다.

이랬을 때, 문제 조건상 1개의 숫자로 만들수 있는 n 후보들의 갯수는 1이다.

0을 0번써서 만드는 건 1로 하자. 

 

이때, i개를 써서 j를 만드는 방법의 갯수는 

(i-1개를 써서 0-j 까지를 만드는 방법의 갯수의 총 합) 으로 나타낼 수 있다.

왜냐면, 10 = 9를 만드는 방법의 수 + 1, 8을 만드는 방법의 수 +2 ... 이런 식으로 나타낼 수 있기 때문이다. 

원래는 10을 만드는 방법의 수 + 0 도 있는데, 이건 모든 숫자가 공통이라 그냥 d[i][0] 처리를 해버렸다. 인덱스 문제가 귀찮아서.

 

따라서, 문제의 정답 코드는 다음과 같다.

 

 

import sys

N,K = [int(i) for i in input().split()]

d = [[0]*201 for _ in range(201)]

q = 1000000000

for i in range(201):
    d[1][i] = 1
    d[i][0] = 1

for i in range(2,K+1):
    for j in range(1,N+1):
        d[i][j] = sum([d[i-1][j-a]%q for a in range(j+1)])
        d[i][j] = d[i][j] %q



print(d[K][N])

더 빠르게 할 수 있다고는 하는데 안함.