[백준][DP] 2225번 합분해

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/2225)

풀이

문제를 읽어보았을 때 꽤 간단한 문제라고 느껴서 바로 점화식을 세웠지만 조건을 하나 놓쳐서 다시 읽어본 문제입니다. 식은 간단히 세울 수 있었습니다 dp[N][K]를 K개의 정수를 더해서 N을 만드는 것이라고 정의를 합니다. 그렇게 되면 dp[N][K] = dp[N-(N또는 보다 작은 정수)][K-1]의 합이 됩니다. 즉 N또는 N보다 작은 숫자를 K-1개로 만들었다면 거기에다가 N을 만들 수 있도록 수를 더해주면 K-1개로 만들 수 있는 수들의 합이 곧 K개의 정수를 더해서 만들 수 있는 경우의 수입니다. 여기서 N 또는이라고 한 이유는 정수 0도 포함되기 때문에 K-1개를 통해서 N을 만들었을 때 해당 수에 0 을 더해주면 K개의 정수를 사용한 것이 되기 때문에 N도 포함해줘야합니다! 제가 처음에 놓쳤던 조건이 0을 포함하지 않아서 예제 입력 20 2를 입력했을 때 19가 나와서 다시 조건을 읽어보고 고쳤습니다. 또 문제를 통해 얻을 수 있는 힌트는 1,000,000,000 으로 나눈 나머지를 출력하라고 하니 값이 매우 커질 수 있다는 걸 알 수 있고 dp 배열을 long long으로 선언해야겠다고 떠올릴 수 있습니다.

코드

https://github.com/kswim/Algorithm/blob/master/DP/2225.cpp