[BOJ] 2225 합분해 (Python / 파이썬)

🧷 문제

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

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하는 문제이다.

🛠 풀이

혼자 풀다가 해결하지 못해 다른 사람들의 풀이를 참고했다.
여러 사람들의 풀이를 보니 이 문제는 DP로 푸는 것과 중복조합을 이용해 푸는 두 가지 방법이 존재한다.

1. DP

Step 1.
 먼저 DP table을 (K x K)의 2차원 테이블로 정의하고, 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 dp[N][K]에 넣어준다.

ex) N = 0, K = 2 일 경우 : 0부터 2까지의 정수 1개를 더해 합이 2가 되는 경우의 수이다.
만들 수 있는 경우의 수는 0+0 한 가지 밖에 없을 것이다. 즉, d[0][2] = 1

ex) N = 1, K = 2 일 경우 : 0부터 2까지의 정수 2개를 더해 합이 2가 되는 경우의 수이다.
만들 수 있는 경우의 수는 0+1, 1+0 두 가지이다. 즉, dp[1][2] = 2

ex) N = 2, K = 2 일 경우 : 0부터 2까지의 정수 2개를 더해 합이 2가 되는 경우의 수이다.
만들 수 있는 경우의 수는 0+2, 1+1, 2+0 세 가지이다. 즉, dp[2][2] = 3

ex) N = 2, K = 3 일 경우 : 0부터 2까지의 정수 3개를 더해 합이 2가 되는 경우의 수이다.
만들 수 있는 경우의 수는 0+0+2, 1+0+1, 0+1+1, 0+2+0, 2+0+0, 1+1+0, 여섯 가지이다. 즉, dp[2][3] = 6

여기에서 K = 3 인 경우는 K = 2 인 경우에서 정수 1개를 더 추가한 것이다.
정리하면, 위의 예에서 dp[2][3]은 0부터 2까지 2개의 정수를 더해 합이 0 ~ 2가 되는 경우에서 부족한 i만큼을 더해준 것이다.
즉, dp[2][3] = dp[0][2] + dp[1][2] + dp[2][2] (각각 부족한 2, 1, 0을 더해준다)

Step 2.
 하지만 위의 방법으로 구하면

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

for문을 삼중으로 돌기 때문에 O(N^3) 에 수렴하는 시간복잡도를 갖는다.

Step 3.
 그렇기 때문에 식을 다시 들여다보게 되면,
dp[N][K] ={dp[0][K-1] + dp[1][K-1] + ... + dp[N-2][K-1] + dp[N-1][K-1]}+ dp[N][K-1]
{dp[0][K-1] + dp[1][K-1] + ... + dp[N-2][K-1] + dp[N-1][K-1]}를 dp[N-1][K] 로 치환할 수 있다.
결과적으로 dp[N][K] = dp[N-1][K] + dp[N][K-1] 이라는 결과를 얻을 수 있고 이걸 통해 원하는 값을 구할 수 있다.

2. 중복조합

Step 1.
 이 문제는 0 ~ N까지의 정수 K개를 더해서 합이 N이 되는 수를 구하는 문제이다.
 중복조합은 n개의 원소에서 r개를 중복을 허락하여 뽑을 때의 가짓수이다. nHr = (n+r-1)Cr

Step 2.
 문제에 적용하면 K개의 정수를 사용하여 N을 만들면 되기 때문에 kHn을 구하면 답을 얻을 수 있다.

Step 3.
kHn = (k+n-1)Cn = (k+n-1)! / (k-1)! * n!

🖊 나의 코드

import sys

if __name__ == "__main__":
    n, k = map(int, input().split())

    dp = [[0]*(k+1) for _ in range(n+1)]

    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]
            dp[i][j] %= 1000000000

    print(dp[n][k])

######중복조합######

import sys

def fac(n):
    res = 1
    for _ in range(1, n+1):
        res *= _
    return res

if __name__ == "__main__":
    n, k = map(int, input().split())
    print((fac(k+n-1) // (fac(k-1) * fac(n))) % 1000000000)