백준 - 2225번 합분해

출처 : 2225번: 합 분해 (acmicpc.net)

2225번: 합분해

---

문제

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

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

입력

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

출력

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

 

---

이런 문제를 만났을때 여러 가지를 생각해볼 수 있습니다. 공식을 찾아서 재귀적으로 풀 수도 있고, 일일이 무식하게 풀어 볼 수 도 있지만.. 제가 혹은 이걸 보시는 분들이 이 문제를 DP로 접근해야 하는 가장 근본적인 이유는 문제를 1부터 시작하면서 횟수를 적어보면 기하급수적으로 커진다는 것을 알 수 있고, 그로 인해 저희는 한 번 계산한 횟수를 다시 계산하지 말고, 다시 이용해야 하는 필요성이 여기에 있습니다.

 

DP로 접근해야한다는 것 자체도 인지하기 힘들지만 일단 인지하고 문제를 풀 때는 손으로 문제를 적으면서 원리를 찾는 것이 가장 이상적입니다.

 

---

원리를 찾아봅시다.

 

그림 1. 합분해 설명

 

 

도표로 간단하게 표시해보니 규칙이 되는대로 간다는것을 알 수 있다.

수의크기  횟수의 길이	0	1	2	3	4	5
1	1	1	1	1	1	1
2	1	2	3	4	5	6
3	1	3	6	10	15	21
4	1	4	10	20	35	56

 

규칙을 찾았으니 규칙에따라 코딩을 해주면 됩니다.

---

2225번 합분해 코딩 내용:

 

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

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

for i in range(1, K + 1):
    for j in range(N + 1):
        if j == 0:
            dp[i][j] = 1
        else:
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000000

    for row in dp:
        print(row)
    print()
print(dp[-1][-1])

else 부분이 보이시나요 좌쪽에서 오는 값과 위쪽에서 오는 값의 합은 자기 자신이다!라는 뜻입니다.

 

---

후기

 

역시 이렇게 글을 쓰면서 설명하면서 복습하니 한 번 더 리마인드 되고, 더 깊게 이해되는 느낌이 받습니다.

다른 분들이 혹여 이문제를 풀 때 이 설명이 도움이 되길 바랍니다.