백준: 2225 합분해

문제

2225번: 합분해

 

문제 풀이

 N까지 숫자 중 K개를 이용해서 N이 되는 경우의 수를 구하는 문제이다. 어떤 방식으로 풀면 좋을지 고민하다가, 단순히 N이 1인 경우부터 시작해서 K가 증가할 경우 경우의 수를 찾아보았다.

 

• N이 1인 경우
  • K에 따라 발생하는 경우의 수
    • 1 : [1] → 1가지
    • 2 : [0 + 1], [1 + 0] → 2가지
    • 3 : [0 + 0 + 1], [0 + 1 + 0], [1 + 0 + 0]  → 3가지
    • 4 : 4가지
• N이 2인 경우
  • K에 따라 발생하는 경우의 수
    • 1 : [2] → 1가지
    • 2 : [0 + 2], [1 + 1], [2 + 0] → 3가지
    • 3 : [0 + 0 + 2], [0 + 2 + 0], [2 + 0 + 0], [0 + 1 + 1], [1 + 1 + 0], [1 + 0 + 1] → 6가지
    • 4 : 10가지

 경우의 수를 일일이 다 찾아보는 것은 상당한 시간을 소요하게 된다. 하지만, N이 1, 2인 경우를 나열해 보면, 모든 경우의 수를 일일이 찾지 않더라도 문제를 풀 수 있음을 알 수 있다.

 

N	K = 1	K = 2	K = 3	K = 4	K = 5
1	1	2	3	4	5
2	1	3	6	10	?

 

 위의 표를 보면 N - 1일 때 K + 1인 경우의 수와 N일 때 K인 경우의 수의 합이 문제를 풀 수 있는 점화식이 된다. 따라서 N이 2인 경우에 K가 5인 경우의 수는 5 + 10으로 15가 되는 것을 알 수 있다.

 

코드

from sys import stdin


if __name__ == '__main__':
    n, k = map(int, stdin.readline().split())
    dp = [[0] * 201 for _ in range(201)]
    divisor = 1000000000

    for i in range(k + 1):
        dp[0][i] = 1

    for i in range(1, n + 1):
        for j in range(1, k + 1):
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % divisor

    print(dp[n][k])