[백준] 합분해 (2225번 JAVA) (!) / 400 - 다이나믹 프로그래밍 1

[백준] 합분해 (2225번 JAVA) (!) / 400 - 다이나믹 프로그래밍 1

---

[접근 방법]

표를 이용하여 경우의 수를 정리 해 보았다.

 

여기서 발견할 수 있는 규칙은 

21 + 35 = 56 으로 도출된다는 것이다.

왼쪽 칸 + 위쪽 칸 = 현재 칸의 규칙을 가지고 있다.

 

이를 DP의 점화식으로 정리한다면,

 

DP[N][K] = DP[N][K-1] + DP[N-1]+[K]

(1 <= N <=200 , 1 <= K <= 200)

 

로 정리 할 수 있다.

 

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        // (1 ≤ N ≤ 200)
        int N = Integer.parseInt(st.nextToken());
        // (1 ≤ K ≤ 200)
        int K = Integer.parseInt(st.nextToken());

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

        // 초기값 설정 
        for(int i=1; i<=K; i++){
            DP[1][i] = i;
        }
        for(int i=1; i<=N; i++){
            DP[i][1] = 1;
        }

        for(int i=2; i<=N; i++){
            for(int j=2; j<=K; j++){
                DP[i][j] = (DP[i][j-1] + DP[i-1][j]) % 1_000_000_000;
            }
        }
        
        bw.write(DP[N][K] + "\n");
        bw.flush();
        bw.close();
    }
}