[백준] 동전 0 [Java/자바]

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        int ans = 0;
        for (int i=n-1; i>=0; i--) {
            ans += k/a[i];
            k %= a[i];
        }
        System.out.println(ans);
    }
}

동전과 지폐가 담긴 배열 a를 거꾸로 돌면서 k를 쪼갤 수 있는 가장 큰 수부터 찾는다.

총 몇장이 필요한지 계산하여 ans에 담아두고

쪼개야 하는 금액을 모듈러(%)를 사용해 다시 설정해준다.

 

제일 기본적인 Greedy Algorithm문제