[알고리즘] 백준 11047 동전 0 - JAVA

www.acmicpc.net/problem/11047

11047번: 동전 0

 

그리디는 매 시점에 최선의 선택을 하는 알고리즘이다.

 

입력으로 오름차순으로 정렬된 동전 배열을 주었기에 배열의 마지막 인덱스부터 반복문을 돌린다.

 

딱히 그리디 알고리즘을 따로 공부하지 않아도 풀 수 있는 문제인 것 같다.

 

코드 설명은 주석으로 달아놨다.

 

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

public class BOJ_11047 {

    static int n;
    static int k;
    static int[] coin;
    static int count = 0;

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

        for (int i = 0; i < n; i++) {
            s = br.readLine();
            coin[i] = Integer.parseInt(s);
        }
        // input end

        // coin 배열은 오름차순으로 정렬되어있으므로 마지막 인덱스부터 반복문 시작
        for (int i = n - 1; i >= 0; i--) {
            // 현재 시점 돈이 coin[i]보다 작아야함
            // 이 시점에 증가하는 동전의 개수는 k / coin[i]의 몫
            // (k = 100, coin[i] = 30)일 경우 동전 3개 쓰고 10원남음
            // 다음 k값은 k / coin[i]의 나머지
            if (k >= coin[i]) {
                count += k / coin[i];
                k = k % coin[i];
            }
        }

        System.out.println(count);
    }
}