[백준] 2225번 [python]

[백준] 2225번 [python]

문제

 

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

2225번: 합분해

해당문제는 DP문제로 점화식을 구하면 풀수있다. 해당 점화식을 구해보도록 하자

N = 4, K = 3라고 가정할때

정수 0을 만들기 위해

갯수 1개인경우는 (0), 1개

갯수 2개인경우는 (0,0), 1개

갯수 3개인경우는 (0,0,0) , 1개이다.

또한 정수 2를 만들기 위해

갯수 1개인경우는 (2), 1개

갯수 2개인경우는 (0,2), (0,2), (1,1), 3개

갯수 3개인경우는 (0,0,2), (0,2,0), (2,0,0), (0,1,1), (1,0,1), (1,1,0), 6개 이다.

위에처럼 정수 0부터 4까지 쭉 나열해본다면 아래 표처럼 정리할수있다.

갯수\정수	0	1	2	3	4
1	1	1	1	1	1
2	1	2	3	4	5
3	1	3	6	10	15

해당 표를 보면 어떤 점화식이 보이지 않는가 ???????/

현재 좌표 = 왼쪽 + 위쪽의 형태가 보인다

다시 말해서 table( i )( j )= table( i-1 )( j ) + table( i )( j-1) 의 점화식을 찾아낼수 있다.

해당 점화식을 활용하여 코드를 구현하자!!

코드

N, K = map(int,input().split())
mapping = [[0 for _ in range(N+1)] for _ in range(K)]
mapping[0][:] = [1 for _ in range(N+1)]
maxV = 1000000000
for k in range(K):
    mapping[k][0] = 1
for j in range(1,N+1):
    for i in range(1,K):
        mapping[i][j] = (mapping[i-1][j] + mapping[i][j-1]) % maxV
print(mapping[-1][-1])