[백준/파이썬] 2225번 합분해

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

2225번: 합분해

중복조합 또는 dp로 해결가능한 문제인데, dp로 풀어보았다.

우선, k가 1일 경우엔 n으로 어떤 수가 와도 경우의 수는 1이다. 그러나 n이 1일 경우, 경우의 수는 k값을 따라간다.

dp 테이블	k = 1	k = 2	k = 3
n = 1	1	2	3
n = 2	1	3
n = 3	1
n = 4	1
n = 5	1

이제 위 dp 테이블을 채워나가면 된다. n=2이고 k=2일 때 가능한 경우는 0+2, 2+0, 1+1 총 3가지 이다.

이는 (2,1)의 경우인 2와 (1,2)의 경우인 0+1, 1+0를 합한 것이라고 볼 수 있다. 물론 숫자는 다르지만, 경우의 수만을 따졌을 때 그러함을 알 수 있다.

결국 점화식은 dp[i][j] = dp[i-1][j] + dp[i][j-1] 임을 도출해낼 수 있다. (테이블을 직접 채우면서 점화식을 세워보시길!)

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

# n은 행, k는 열
for i in range(1,n+1):
    dp[i][1] = 1
    
for i in range(1,k+1):
    dp[1][i] = i
    
for i in range(2,n+1):
    for j in range(2,k+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
print(dp[n][k]%1000000000)