이번에 풀어본 문제는
백준 2225번 합분해 입니다.

📕 문제 링크

❗️코드

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

public 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[N+1][K+1];
        for(int i = 1; i <= N; ++i) dp[i][1] = 1;
        for(int i = 1; i <= K; ++i) dp[1][i] = i;

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

📝 풀이

0부터 N까지의 수 중에서 K개를 더해 N을 만들 수 있는 경우의 수를 구하는 문제입니다.
점화식을 구하기 위해 몇 가지 예시를 들어보면 규칙을 찾을 수 있습니다.
보기 쉽게 표를 그려 값을 비교해보면 dp[N][K] = dp[N-1][K] + dp[N][K-1]의 규칙이 생기며, 이를 적용시킨 2차원 배열을 만들어주면 해결됩니다.

📜 후기

조금의 노가다가 필요하지만 생각보다 금방 규칙을 찾을 수 있었습니다. ^^