2225번 0~N까지의 정수 K개를 더해서 합이 N이 되는 경우의 수 구하기

2시간 걸림. 근데 못풀었다고 봐야함;; dp[i][j] : i개를 더해서 j가 되는 경우의 수 이 위 식은 빠르게 구했는데 그 뒤가 진도가 안나가서 검색해서 힌트봄ㅠ_ㅠ dp[i][j] = dp[i-1][0] + dp[i-1][1] + … + dp[i-1][j] 인데 왜 그러냐면. i개를 더해서 j가 되려면 i-1개를 더해서 0이 되는 경우에 마지막 정수를 j를 더해주면 i개를 더해서 j가 되므로. i-1개를 더해서 10이 됐으면 -> dp[i-1][10] 여기에 (j-10)만 마지막 정수로 더해주면 `dp[i][j] 이 됨. 나는 이 k-1개까지 구한 값에 j가 되기 위해 필요한 마지막 정수 하나만 더해주면 j가 되는 그 생각을 못함ㅠ_ㅠ

그리고 마지막에 제출했는데 틀린 이유가 int로 안하고 long으로 바꾸고 중간에도 mod 연산 넣으니까 풀림ㄷㄷ;; 이거 땜에 왜 안되는지 시간 한참 썼네ㅠ_ㅠ 모듈러 연산 있으면 int를 꼭 long으로 바꾸고 중간에도 넣자!

import java.util.*;  
import java.io.*;  
  
public class BJ_2225 {  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        int n = Integer.parseInt(st.nextToken());  
        int k = Integer.parseInt(st.nextToken());  
        int mod = 1_000_000_000;  
        long[][] dp = new long[k+1][n+1];  
  
        //dp[i][j] : i개를 더해서 j가 되는 경우의 수  
        for(int i=0; i<=k; i++) {  
            dp[i][0] = 1;  
        }  
  
        for(int i=1; i<=k; i++) {  
            for(int j=1; j<=n; j++) {  
                for(int num=0; num<=j; num++) {  
                    dp[i][j] += dp[i - 1][num] % mod;  
                }  
            }  
        }  
  
        System.out.println(dp[k][n] % mod);  
    }  
}