[BOJ] 2294. 동전 2

DP문제이다.

코딩테스트에 나왔던 문제이다. 그 당시 효율성을 해결하지 못하여 풀지 못했어서 다시 풀어보았다. 맨처음 문제를 보고 자연스럽게 바텀업이 생각났고 DP로 접근하게 되었다. 다음과 같은 점화식으로 DP를 풀었다.

DP[i] = min(DP[i], DP[i-현재 코인의 값] + 1) 과 같은 점화식을 얻을 수 있었고 이것을 이용하여 모든 코인에 대하여 처리해주는 방식으로 풀었다.

package study4;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main_bj_2294_동전2 {
    static int N,K;
    static int[] dp;
    static int[] coins;
    static int answer;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N=Integer.parseInt(st.nextToken());
        K=Integer.parseInt(st.nextToken());
    
        dp=new int[K+1];
        for(int i=1;i<=K;i++)
            dp[i]=Integer.MAX_VALUE/2;
        
        coins=new int[N];
        for(int i=0;i<N;i++) {
            coins[i]=Integer.parseInt(br.readLine());
        }
        
        func();
    
        if(dp[K]==Integer.MAX_VALUE/2)
            System.out.println(-1);
        else
            System.out.println(dp[K]);
    }
    
    static void func() {
        Arrays.sort(coins);
        
        dp[0]=0;
        for(int coin : coins) {
            for(int i=coin;i<=K;i++) {
                dp[i]=Math.min(dp[i], dp[i-coin]+1);
            }
        }
    }
}