백준 - 2225번 합분해

코드

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        int[][] dp = new int[K + 1][N + 1];

        for (int i = 0; i <= K; i++) {
              dp[i][0] = 1;
        }
        Arrays.fill(dp[1],1);
        for (int i = 1; i <= K; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000;
            }
        }
        System.out.println(dp[K][N]);

    }

}

해설

😎전형적인 dp문제이다. 수열만 찾을 수 있다면 dp가 쉽지만 찾는게 쉽지가 않다.

위 문제를 분해해보면 dp[i][j]는 i = K개 고르기 , j=합 만들기 이며 이걸 분할해보면 (dp[i-1][0] ~~~ dp[i-1][j])로 쪼갤수 있다. 이 때 dp[i-1][0]~dp[i-1][j-1] 은 dp[i][j-1]과 같기에 위와 같은 공식이 나오게 된것이다.🫡

출처 : 백준 - 합분해