백준 2225번 - 합분해(java)

https://www.acmicpc.net/problem/2225

 

 

늘 어려운 DP,, 이번에도 한번에 풀지 못하고 힌트를 받고 풀었다.

언제쯤 나는 내 혼자의 힘으로 DP를 풀 수 있을 것인가,,흑

💡 아이디어

• f(n,k)로 표를 그리면서 규칙을 찾았다.

💡 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2225_합분해2 {
    static int N, K;
    static long arr[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new long[N + 1][K + 1];

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

        }
        System.out.println(arr[N][K] % 1000000000);
    }
}