[JAVA] 백준 11047번 : 동전 0

https://www.acmicpc.net/problem/11047
이 문제는 그리디 알고리즘을 사용하여 푸는 문제이다.

Greedy Algorithm(그리디 알고리즘)

그리디 알고리즘은 탐욕스러운 알고리즘이다. 즉, 가장 탐욕스러운 방법을 선택한다는 것이다. 이 의미는 '선택의 순간'이 올 때마다 그 상황에서의 가장 좋은 것을 선택한다는 의미이다. 과거와 미래를 고려하지 않고 당시 순간의 가장 좋은 것을 선택하는 것이다.

정답 코드

처음에는 정답을 제대로 읽지 않아서 동전이 각 하나씩만 주어지는 줄 알았다 ㅠㅠ
하지만, 동전의 개수는 충분히 주어지므로 같은 동전을 여러번 중복해서 사용할 수 있다.
그래서 K보다 작은 수 중 최대로 사용할 수 있는 개수를 '몫'을 이용하여 구하고, 더 적은 금액을 '나머지'를 이용하여 K값에 새로 저장해 주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
        Integer[] coins = new Integer[N]; //reverseOrder를 사용하기 위하여 int가 아니라 Integer로 선언
        int cnt = 0; //동전개수
        for (int i = 0; i < N; i++) {
            coins[i] = Integer.parseInt(br.readLine()); //각각의 동전을 많이 가지고 있음
        }
        Arrays.sort(coins, Collections.reverseOrder()); //내림차순으로 정렬
        for (int i = 0; i < N; i++) {
            if (coins[i] <= K) { //동전이 K보다 작거나 같을 때
                cnt = cnt + K / coins[i]; //나누어지는 개수 -> 몫
                K = K % coins[i]; //나머지
            }
        }
        System.out.println(cnt);
        br.close();
    }
}