[DP] 백준 #2225 / 합분해

---

---

문제는 위와 같다. 처음엔 초 난감... 했는데 스티커 메모장에다가 이렇게 적어보면서 정리해봤다.

그렇다. 생각보다 단순한 문제였다. 이중 DP배열이 필요하고, 그림으로 나타내면 다음과 같이 나타낼 수 있다.

(i , j) 좌표의 값을 구하려면, (i, j-1) + (i-1, j) 값이 필요하다. 너무 쉬운 문제라서 더 이상의 설명은 생략해도 될법하다.

라고는 했으나 사실 틀렸었는데, Output 조건을 잘 보면, 답을 1,000,000,000로 나눈 나머지라고 했으니까 이런 조건좀 빼먹지 말자.

[Code]

import java.util.Scanner;
public class boj_2225 {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int K = sc.nextInt();
        int dp[][] = new int[201][201];
        
        for(int i=1;i<=K;i++) 
            dp[0][i] = 1;
        for(int i=1;i<=N;i++) {
            for(int j=1;j<=K;j++) {
                dp[i][j] = (dp[i][j-1]+ dp[i-1][j])%1000000000;
            }
        }
        System.out.println(dp[N][K]);
    }
}