[백준, 자바] 2225번- 합분해

문제 링크
https://www.acmicpc.net/problem/2225

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int k = Integer.parseInt(arr[1]);
        int MOD = 1000_000_000;

        int[][] dp = new int[k+1][n+1];
        Arrays.fill(dp[1], 1);
        for (int i = 1; i <= k; i++) dp[i][0] = 1;

        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
                dp[i][j] %= MOD;
            }
        }
        System.out.println(dp[k][n]);
    }
}

풀이
사실 2차원 dp를 선언하고 본인의 왼쪽 값과 위쪽 값을 더한 값으로 본인을 갱신하면 된다.
근데 그 점화식에 도달하기에 실패한 부분;;

나는 처음부터 4개의 값으로 표현한 데이터를 누적할까를 생각했는데
풀이는 1개의 값으로 표현, 2개의 값으로 표현, 3개의 값으로 표현.... 결과를 재사용하는 원리였다.

2개의 값으로 조합하는 경우를 더 까보면 아래처럼 되는데,

사실 2개 경우까지만 봐도 답이 나오더라.