[백준]11047 - 동전 0 문제 풀이(Java,자바)

11047번: 동전 0

들어가며

그리디 기법으로 풀면 쉽게 접근할 수 있는 문제이다.

 

코드

public class 백준11047_동전0 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = reader.readLine().split(" ");

        int n = Integer.parseInt(inputs[0]);
        int k = Integer.parseInt(inputs[1]);

        ArrayList<Integer> arr = new ArrayList<>();

        for (int i = 0; i < n; i++){
            arr.add(Integer.parseInt(reader.readLine()));
        }
        Collections.sort(arr, Comparator.reverseOrder());

        int index = 0;
        int result = 0;

        while (k != 0){
            int cur = arr.get(index);
            int curAmount = k / cur;
            if (curAmount > 0){
                k -= cur * curAmount;
                result += curAmount;
            }
            index++;
        }
        System.out.println(result);
    }
}

풀이

결국 동전의 개수를 최소로 맞출려면 제일 비싼 금액부터 쳐내야 한다.

Collections.sort(arr, Comparator.reverseOrder());

 

그러기 위해 오름차순 입력을 내림차순으로 정렬 해야한다.

그 이후 반복문에 진입을 하는데,

index는 해당 금액을 다 사용했을 경우 넘어가주면 되고,

한번 돌 때마다 만들어진 동전들의 금액을 k에서 빼주고 넘어가면 된다.

 

그렇게 정답을 구할 수 있다.