[BOJ 2225] 합분해

문제 링크 : https://www.acmicpc.net/problem/2225

문제

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

$0$부터 $N$까지의 정수 $K$개를 더해서 합이 $N$이 되는 경우의 수를 구하는 문제다. 덧셈의 순서가 다르면 다른 경우로 취급하며, $0$도 사용할 수 있다는 점에 유의해야 한다.

$K$개의 정수를 선택해서 합을 만드는 과정은, 마지막에 더한 수가 무엇인지에 따라 이전 상태로부터 유추해낼 수 있다. 즉, 큰 문제를 작은 부분 문제로 쪼개서 해결하는 다이나믹 프로그래밍 문제로 정의할 수 있다.

점화식을 세우기 위해 $DP[n][k]$를 “정수 $k$개를 사용하여 합 $n$을 만드는 경우의 수”라고 정의하자.

만약 우리가 마지막 $k$번째 수로 $l$ $(0 \leq l \leq n)$을 선택했다고 가정해보자. 그렇다면 그 이전 단계에서는 $k-1$개의 수를 사용하여 합 $n-l$을 만들어야 했을 것이다. 가능한 모든 $l$에 대해 이 경우의 수를 더해주면 현재 상태의 답을 구할 수 있다.

이를 수식으로 표현하면 다음과 같다.

\[DP[n][k] = \sum_{l=0}^{n} DP[n-l][k-1]\]

$N$과 $K$의 범위가 최대 200으로 작기 때문에, 위 점화식을 그대로 3중 반복문으로 구현해도 연산 횟수는 대략 $200^3 = 8\,000\,000$번 정도로 시간 제한 2초 안에 충분히 통과할 수 있다.

초기값으로는 $DP[0][k] = 1$ ($0$을 $k$개 더하면 합이 $0$), $DP[n][1] = 1$ ($n$ 하나만 사용하면 합이 $n$) 등으로 설정하고 반복문을 돌리면 된다. 문제 조건에 따라 $1\,000\,000\,000$으로 나눈 나머지를 저장하는 것을 잊지 말자.

소스코드

Github Link : Source Code

참고 알고리즘 : 다이나믹 프로그래밍