[Algorithm] 99클럽 코테 스터디 24일차 TIL | 백준_합분해(2225번)

📝문제

 

💡풀이

dp[k][n] : 0부터 n까지의 수 중 k개의 수를 합해 n을 만들 수 있는 개수

dp[1][0] = 1  (0)

dp[2][0] = 1 (0+0)

dp[3][0] = 1 (0+0+0)

dp[4][0] = 1 (0+0+0+0)

 

dp[1][1] = 1 (1)

dp[2][1] = 2 (0+1), (1+0)

dp[3][1] = 3 (0+1+0), (1+0+0), (0+0+1)

dp[4][1] = 4 (0+1+0+0), (1+0+0+0), (0+0+1+0), (0+0+0+1)

 

dp[1][2] = 1 (2)

dp[2][2] = 3 (0+2), (2+0), (1+1)

dp[3][2] = 6 (0+2+0), (2+0+0), (0+0+2), (0+1+1), (1+1+0), (1+0+1)

dp[4][2] = 10 (0+2+0+0), (2+0+0+0), (0+0+2+0), (0+1+1+0), (1+1+0+0), (1+0+1+0), (0+1+0+1), (1+0+0+1), (0+0+1+1), (0+0+0+2)

 

아래와 같은 점화식 도출

점화식

dp[k][n]=dp[k−1][n]+dp[k][n−1]

 

전체 풀이

import java.util.*;
import java.io.*;
class Main{
    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[][] dp = new int[K+1][N+1];

        for(int i = 1; i <= K; i++){
            dp[i][0] = 1;
        }

        for(int i = 1; i <= K; i++){
            for(int j = 1; j <= N; j++){
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000000;
            }
        }

        System.out.println(dp[K][N]);
    }
}

 

🤔Review

점화식 마스터가 되고싶어요..