DP

백준 2225번을 Java를 이용해 풀어보았다.
DP 엿 먹어

문제 링크 첨부한다.
https://www.acmicpc.net/problem/2225

---

점화식 찾기

가장 많이 나오는 형태라서 여러 숫자의 합을 두 개의 합만으로 바꾸는 원리를 이용해서 점화식을 찾으려 했는데 결국 못 찾았다.

항상 다른 사람의 풀이를 보고 나면 '아...' 하지만 어쨌든 못 푼 것은 못 푼 것...ㅠ

0~N까지의 수를 K개 사용해서 N을 만들어내는 점화식을 만들기 위해 int[][] dp = new int[K+1][N+1] 을 선언했다.

dp[k][n]은 k개의 수로 n을 만들어 낼 수 있는 경우의 수를 의미하는 것이다.

두 개의 수만으로 n을 만든다고 생각하면 다음과 같은 점화식을 도출할 수 있다.

dp[k][n] = dp[k-1][n] + dp[k][n-1]

k-1개의 수로 n을 만들고 거기에 0을 더해주면 되고, k개의 수로 n-1을 만들고 거기에 1을 더하면 되는 로직이다.

코드는 아래와 같다.

import java.io.*;
import java.util.StringTokenizer;

public class boj2225 {
    static int N,K;
    static int[][] dp;

    static Integer solution(){
        dp = new int[K+1][N+1];
        for(int i=1; i<=K; i++)
            dp[i][1] = i;

        for(int i=1; i<=N; i++)
            dp[1][i] = 1;

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

    public static void main(String[] args) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        N = Integer.parseInt(stk.nextToken());
        K = Integer.parseInt(stk.nextToken());
        System.out.println(solution());
    }
}

---

DP 잘 풀고 싶다.
씨방!