[코딩 테스트/백준 알고리즘] 11047번 - 동전 0 (Java, 자바 풀이)

문제

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

11047번: 동전 0

---

문제 설명

---

문제 풀이

 가치가 가장 큰 동전부터 연산을 통해. 금액을 줄여가면서 해결했다.

 순차적으로 위에서부터 내려오면 풀리는 문제라서 그리디 알고리즘 문제 치고는 수월하게 해결했다.

---

코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int index = N - 1;
        int count = 0;
        int[] money = new int[N];
        
        //입력
        for(int i = 0; i < N; i++) {
            money[i] = sc.nextInt();
        }
        
        //연산
        while(K != 0) {
            if(money[index] <= K) {
                int cnt = K / money[index];
                K -= money[index] * cnt;
                count += cnt;
                index--;
            }
            else
                index--;
        }
        
        //결과 출력
        System.out.println(count);
    }
}