<aside> 💡 그리디 알고리즘은 잘 따져보지 않으면 반례가 생길 수 있다. (최적의 해를 보장하지 않음) 구현이 간단하지만 꼭 문제에서 주어진 조건을 필수로 확인하고 풀자

</aside>

문제 설명

문제 분석

슈도코드

구현

public class 동전_개수의_최솟값_구하기_11047 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt(); // 동전의 종류
        int K = scan.nextInt(); // 가격의 합
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = scan.nextInt();
        }

        int count = 0;
        for (int i = N - 1; i >= 0; i--) {
            if (arr[i] <= K) {
                count += K / arr[i];
                K %= arr[i];
            }
        }

        System.out.println(count);
    }
}