[JAVA / 자바] 백준 11047번_동전 0

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

11047번: 동전 0

---

import java.util.Scanner;

public class Main {
    static int N;
    static int[] coins;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        long K = sc.nextLong();
        int cnt = 0;
        coins = new int[N];
        for (int i = N-1; i >= 0; i--) {
            coins[i] = sc.nextInt();
        }
        for (int coin : coins) {
            if(K / coin > 0){
                cnt += (K / coin);
                K %= coin;
                if(K == 0) break;
            }
        }
        System.out.println(cnt);
    }
}

💡 그리디

풀이 

1. 동전 가치 기준 오름차순으로 주어짐 -> 내림차순으로 배열에 저장함

2. 제일 큰 가치부터 최대한 몫 할당