[Java] 백준-11047 동전 0 (그리디 알고리즘)

11047번: 동전 0

이번 문제는 그리디 알고리즘을 사용하여 문제를 푼다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

// 백준 11047 동전 0
public class Coin0 {
    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());
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0; i<N; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }
        br.close();

        int totalCount = 0;
        // 문제에서 오름차순으로 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000을 입력받아
        // 순서대로 ArrayList에 들어갔지만
        // 최소 동전갯수를 구하기 위해서는 역순으로 (50000 > 10000 > 5000 > 1000 > ~ ) 나눠준다
        for (int i = list.size()-1; i >= 0; i--) {
            // K의 값이 list.get(i)보다 작다면 i--
            if(list.get(i) <= K) {
                int coinCount = K / list.get(i);
                totalCount += coinCount;
                
                K %= list.get(i);
                //K -= list.get(i) * coinCount;
            } 
            // K의 값이 0이라면 더이상 실행할 필요가 없으므로 break;
            else if (K==0) {
                break;
            }
        }
        System.out.println(totalCount);
    }