[백준/Python3] 2225 합분해

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

풀이

0 부터 N 까지의 수 중 K개를 더해 합이 N이 되는 경우의 수를 구하는 문제다. 이때 수를 중복해서 사용할 수 있으며 순서가 바뀔 경우 다른 경우로 여긴다.

이 문제는 DP Table을 이용해 해결할 수 있다. 2차원 테이블을 이용해 DP Table을 만들고 이는,

dp[K][N] = K개의 수를 더해 N을 만들 수 있는 모든 경우의 수 

0이 포함되고 순서가 바뀌는 경우는 다른 경우로 여기기 때문에 N까지의 수를 K개의 항으로 나타낸 경우의 수는 무조건 K개 이상이다. 때문에

dp = [[k for _ in range(N+1)] for k in range(K+1)]

로 초기화할 수 있다.

이를 표로 구현하면 위와 같다.

위 표에서 K >= 2 && N >= 2에서 특정 규칙을 발견할 수 있으며 이는 다음과 같다.

dp[K][N] = dp[K-1][N] + dp[K][N-1])

코드

# Initial
N, K = map(int, input().split())
mod = 1000000000
answer = 0

# Make DP Table
# 0 을 조합해 무조건 N번째 수는 K개 이상이 나올 수 있음
dp = [[k for _ in range(N+1)] for k in range(K+1)]

for k in range(2, K + 1):
    for i in range(2, N+1):
        dp[k][i] = (dp[k-1][i] + dp[k][i-1]) % mod

# Answer
answer = dp[K][N]
print(answer % mod)