동전 2 - 2294번

---

풀이 방법 

동적 계획법으로 bottom-up 방법을 사용했다.

우선 100001로 초기화 시켜주고 만들수 있는 coins 에 넣은 수들로 비교해가며 최소 횟수를 구해주었다.

 

내 풀이

package com.company;

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

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[] coins = new int[n];
        int[] dp = new int[k + 1];

        Arrays.fill(dp, 100001);

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            coins[i] = Integer.parseInt(st.nextToken());
            if (k + 1 > coins[i])
                dp[coins[i]] = 1;
        }

        dp[0] = 0;

        for (int i = 1; i <= k; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i - coins[j] >= 0)
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }

        if (dp[k] == 100001)
            System.out.println(-1);
        else
            System.out.println(dp[k]);
    }
}