백준 2294 (동전 2) <배낭>

문제

2294번: 동전 2

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

예를 들어 동전이 3개 주어지고, 각각 1, 5, 12 이고, k = 15이면 정답은 3이다.

---

전형적인 배낭 문제이다.

int []coin = new int[n+1];
        int []dp = new int[k+1];

        for(int i=1;i<=k;i++){
            dp[i] = 10001;
        }

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine());
            coin[i] = Integer.parseInt(st.nextToken());
            for(int j = coin[i];j<=k;j++){
                dp[j] = Math.min(dp[j], dp[j-coin[i]] + 1);
            }
        }

---

전체 코드이다.

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

        for(int i=1;i<=k;i++){
            dp[i] = 10001;
        }

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine());
            coin[i] = Integer.parseInt(st.nextToken());
            for(int j = coin[i];j<=k;j++){
                dp[j] = Math.min(dp[j], dp[j-coin[i]] + 1);
            }
        }

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