[Dev-Ping9] 백준 11047번 - 동전 0 (Java)

 

# 문제 설명

 knapsack 문제 유형이다.

 심지어 배수형태로 이루어져 있기 때문에, 제일 큰 값부터 차례로 탐색하는 방식을 택하면 된다.

 

 

 

# 코드 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
    static int[] coins;

    

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        Integer k = Integer.parseInt(st.nextToken());

        coins=new int[n];
        for(int i=0; i<n; i++){
            coins[i]=Integer.parseInt(br.readLine());
        }

        int cnt=0;
        while(k!=0){
            for(int i=n-1; i>=0; i--){
                if(k/coins[i]>=1){
                    int temp= k/coins[i];
                    k-=temp*coins[i];
                    cnt+=temp;
                }
            }
        }

        System.out.println(cnt);

        
    }
}