[백준/python] 2225: 합분해

- 문제

 

- 제출

주어지는 정수 N & K 가 모두 1 이상 200 이하의 수임을 감안하여 저장공간 (cache)를 먼저 정의한다.

 

1. N == 1인 경우 

     0 또는 1을 K개 가지고 1을 만들어야 하므로, 1 하나와 K-1개의 경우만 존재한다. 이때, 문제에서 덧셈의 순서가 바뀐 경우는 다른 경우로 센다고 했으므로 모든 K에 대해 K개의 경우가 존재한다.

 

2. K == 1인 경우

     [0,N] 사이의 정수 1개를 가지고 N을 나타내야 하므로 모든 N에 대하여 1 경우만 존재한다.

 

3. 그 외의 모든 경우

     다른 경우는 어느 정도의 (N, K) 조합에 대해 표를 구성해보면 쉽게 점화식을 얻을 수 있다. 

     찾아낸 점화식 => cache[i][j] = cache[i-1][j] + cache[i][j-1] ( N & K가 2 이상일 때 )

 

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

def devidingSum(N,K):
    cache = [[0]*(201) for _ in range(201)]  # N<=200 && K<=200
    
    for i in range(1,201):
        cache[1][i] = i   
    for i in range(1,201):
        cache[i][1] = 1
        
    for i in range(2,201):
        for j in range(2,201):
            cache[i][j] = cache[i-1][j] + cache[i][j-1]

    return cache[N][K]

print(devidingSum(N,K)%mod)

 

그나마 빨리 풀어낸 다이나믹 프로그래밍 알고리즘 문제..ㅎ