[Python - Dynamic Programming] 2225 합분해

📌 문제

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

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

📌 입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

📌 출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

📌 문제 풀이

👨‍🏫 접근

색상환 문제랑 비슷한 느낌의 문제. 주어진 수를 여러 가지 수의 조합으로 만들 수 있는 경우의 수를 구해야 한다.

 

다이나믹 프로그래밍으로 각각 상황을 저장한다. k개를 선택한 상황에서 n - i를 만드는 경우로 생각하면 dp 테이블을 만들 수 있다.

 

왜냐하면, 20을 2개의 수로 나누어서 구하는 것은 0을 1개의 수로 만드는 것, 1을 1개의 수로 만드는 것, ... , 19를 1개의 수로 만드는 것, 20을 1개의 수로 만드는 것으로 분할해서 생각할 수 있기 때문이다. 그래서 dp 테이블은 [정수 N][선택한 개수 K] 이렇게 테이블을 생성할 수 있다.

 

그런 다음, 두 가지 갈래로 나누어서 테이블의 값을 갱신해 나간다. n에서 0을 빼고 k에 1을 빼는 경우와, n에서 1을 빼고 k를 유지하는 경우이다.

 

전자를 다른 방식으로 보면 [n][k - 1]로 볼 수 있다. 이것은, 정수 N을 N + 0으로 처리하여 k - 1의 기회가 있을 때의 경우의 수이다. 0을 더하기 때문에 k의 기회를 하나 줄인다.

 

후자를 다른 방식으로 보면 [n - 1][k]로 볼 수 있다. 이것은, 정수가 N - 1이고 k의 기회가 있을 때의 경우의 수이다. 사실 이 경우에는 반복문을 통해 이해해야 한다. 앞선 설명들을 보면 $d[n][k] = d[n][k - 1] + d[n - 1][k]$이다. 여기서 $d[n - 1][k]$가 의문이다. 그런데 $d[n][k] = d[n - 0][k - 1] + d[n - 1][k - 1] + ··· + d[1][k - 1] + d[0][k - 1]$ 이기 때문에 $d[n - 1][k] = d[n - 1][k - 1] + d[n - 2][k - 1] + ··· + d[1][k - 1] + d[0][k - 1]$도 성립한다.

 

따라서, $d[n][k] = d[n][k - 1] + d[n - 1][k] = d[n][k - 1] + (d[n - 1][k - 1] + d[n - 2][k - 1] + ··· + d[1][k - 1] + d[0][k - 1]) = d[n][k]$이다. 그렇기 때문에 점화식은 $d[n][k] = d[n][k - 1] + d[n - 1][k]$로 세울 수 있다.

 

그러면 이 점화식을 사용해서 다이나믹 프로그래밍을 해보자~!

👨‍🏫 문제 풀이

📄 전체 코드

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

for i in range(1, n + 1):
    for j in range(1, k + 1):
        if j == 1:
            d[i][j] = 1
        elif i == 1:
            d[i][j] = j
        else:
            d[i][j] = (d[i - 1][j] + d[i][j - 1]) % div

print(d[n][k])

📄 준비

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

📄 풀이

for i in range(1, n + 1):
    for j in range(1, k + 1):
        if j == 1:
            d[i][j] = 1
        elif i == 1:
            d[i][j] = j
        else:
            d[i][j] = (d[i - 1][j] + d[i][j - 1]) % div

print(d[n][k])

1개의 숫자를 통해 i의 정수를 찾는 경우의 수는 1개이므로 1을 저장하고, 1을 j개의 숫자로 만드는 것도 1, 1 + 0, 0 + 1 으로 j개씩 늘어나기 때문에 j로 갱신해준다.

 

둘의 상황이 아니라면 우리가 세운 점화식을 통해 문제를 푼다.

📌 총평

꿀잼꿀잼대꿀쨈