문제

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으로 나눈 나머지를 출력한다.

예제 입력 1
20 2
예제 출력 1
21

예제 입력 2
6 4
예제 출력 2
84

접근

이차원 long 타입 배열을 선언하고, dp[i][j]에 정수 i개를 더해서 합이 j가 되는 경우의 수를 메모이제이션하면 된다.
더해지는 정수 i개 중에 하나가 될 수 있는 수는 0 이상 j 이하일 것이다.(j를 초과하는 수를 더해 버리면 전체 합이 j를 넘어가니까.)
따라서,

dp[i][j] 
= dp[i - 1][j - 0] + dp[i - 1][j - 1] + dp[i - 1][j - 2] ... + dp[i - 1][j - j]

위와 같이 dp[i][j]를 구할 수 있다.

구현

import java.io.*;
import java.util.*;

class Main {
    final static long MOD = 1_000_000_000;
    static int N;
    static long[][] dp; // dp[i][j]: 정수 i개를 더해서 합이 j가 되는 경우의 수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        dp = new long[K + 1][N + 1];
        System.out.println(dynamicProgramming(K, N));
    }

    private static long dynamicProgramming(int count, int targetSum) {
        if (count == 1) {
            if (targetSum <= N) {
                return 1;
            }
            return 0;
        }
        if (dp[count][targetSum] == 0) {
            for (int i = 0; i <= targetSum; i++) {
                dp[count][targetSum] += (dynamicProgramming(count - 1, targetSum - i) % MOD);
                dp[count][targetSum] %= MOD;
            }
        }
        return dp[count][targetSum];
    }
}

재귀 호출 후 모듈러 연산을 수행한 상태로dp[count][targetSum] 배열에 값을 누적했더라도 누적한 다음 모듈러 연산을 한 번 더 해줘야 그 다음 누적 시 오버플로우가 나지 않는다...!