DP

백준 2293번을 Java를 이용해 풀어보았다. DP는 평생 내 힘으로 못 풀 것 같다...

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

---

점화식 찾기

특정 값들을 계속해서 갱신해나가며 이미 구했던 값들을 다시 구할 필요없이 점화식을 찾아주는 것이 핵심이다.

문제에서 입력으로 주어지는 동전의 가치 순서대로 dp 값들을 갱신해나가며 마지막 입력값까지 주어지고 나서의 dp[k]의 값을 출력하면 된다.

점화식은 다음과 같다.
dp[i] += dp[i-coin]

이미 구했던 dp[i] 값에 추가로 들어온 동전을 이용하면 몇 개의 경우가 더 추가되는지를 계속 갱신해주는 것이다.

이를 코드로 표현하면 다음과 같다.

num = new int[n+1];
dp = new int[k+1];
dp[0] = 1;

for(int i=1; i<=n; i++) {
       num[i] = Integer.parseInt(bfr.readLine());
       for(int j=num[i]; j<=k; j++){
           dp[j] += dp[j-num[i]];
       }
   }

System.out.println(dp[k]);

여기서 dp[0]의 역할은 입력으로 들어온 동전 단 하나만으로 표현할 때 기본적으로 1 경우가 추가되는 의미다.

10원 짜리 동전으로 10원을 표현하면 단 한 가지 경우가 나오는 것과 같이 말이다.

아래는 내가 제출한 코드다.

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

public class boj2293 {
    static int n,k;
    static int[] num;
    static int[] dp;

    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());
        num = new int[n+1];
        dp = new int[k+1];
        dp[0] = 1;

        for(int i=1; i<=n; i++) {
            num[i] = Integer.parseInt(bfr.readLine());
            for(int j=num[i]; j<=k; j++){
                dp[j] += dp[j-num[i]];
            }
        }

        System.out.println(dp[k]);
    }
}

---

제발 내 힘으로 한 번이라도 풀어보고 싶다... 씨...