[BOJ/Greedy] 백준 11047 - 동전 0 (Java)

11047 - 동전 0

https://www.acmicpc.net/problem/11047

문제

동전 총 N종류 -> 적절히 사용해서 가치의 합을 K로 만들려고 함
=> 필요한 동전 개수의 최솟값?

입력
첫째 줄: N, K (1 <= N <= 10, 1 <= K <= 100,000,000)
둘째 줄부터 ~ N개의 줄: 동전의 가치 $A_i$ 오름차순
(1 <= $A_i$ <= 1,000,000, $A_1$ = 1, i >= 2인 경우에 $A_i%는 $A_{i-1}$의 배수) 
출력: K원을 만드는데 필요한 동전 개수의 최솟값

---

풀이

가장 큰 가치 동전부터 최대한 많이 사용

int min = 0;
for (int i = N - 1; i >= 0; i--) { 
    if (A[i] <= K) {
        min += (K / A[i]);  // 해당 동전을 최대한 많이 사용
        K %= A[i];          // 남은 금액 갱신
    }
}

---

코드

import java.io.*;
import java.util.*;

// 동전 0
public class boj_11047 {
    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[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }

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

        System.out.println(min);
    }
}