백준 2225번 파이썬 문제풀이(DP - 합분해)

---

위 문제도 역시 파이썬의 itertools.product 내장 함수를 이용하여 K개씩 뽑아서 그합이 N과 같으면 개수를 더하는 식으로 풀어봤으나 역시나 시간초과가 발생했다. 그렇다면 역시 DP문제이기에 조건을 찾아야 한다.

N이 1일때부터~쭉 K가 1일때부터 해서 2차원 표와 같이 그려보면 다음과 같은 그림이 나온다. 먼저 그림을 보고 설명을 하겠다.

 

	n = 1	n = 2	n = 3	n = 4	n = 5
k = 1	1	1	1	1	1	...
k = 2	2	3	4	5	6	...
k = 3	3	6	10	15	21	...

N과 K의 관계에 대해 생각해보자.

N이 1일때는 무조건 K가 1씩 증가한다.

ex) k = 2 이고 n = 1 이면 (0, 1) (1, 0) 2개

ex) k = 4 이고 n = 1 이면 (0, 0, 0, 1) (0, 0, 1, 0) (0, 1, 0, 0) (1, 0, 0, 0) 4개

 

그러나 K가 1일 때는 N은 무조건 1이다. (N 자신 1개)

 

그렇다면 위의 표를 다시보자. 규칙이 보이기 시작한다. 왼쪽 위쪽에 있는 대각선으로 더한 합이 오른쪽아래 값하고 동일하다는 것이다. 이것을 점화식으로 나타내면 다음과 같다.

 

dp[n][k] = dp[n-1][k] + dp[n][k-1] (단, n,k >=2 일때 성립)

 

이것을 이용하면 쉽게 문제를 해결할 수 있다.

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

# 모든 값을 1로 초기화한다.(K가 1일때 N의 값과 관계없이 개수는 1개이기 때문)
dp = [[1] * (K + 1) for _ in range(N + 1)]

# N이 1일 때의 개수는 K값과 동일하기 때문에 K값으로 초기화
for a in range(1, K + 1):
    dp[1][a] = a

# N,K를 2부터 돌아준다.(점화식이 N,K >=2 일때부터 성립하기 때문)
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)