[백준] 11047번 - 동전 0

 

그리디 알고리즘 중 거스름돈 알고리즘을 이용한 간단한 문제이다. 가장 큰 금액부터 비교해가며 금액을 제외하고, 그 카운트를 출력해주어서 해결하였다.

 

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

public class p11047 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		int[] ary = new int[a];

		for (int i = 0; i < a; i++) {
			ary[i] = Integer.parseInt(br.readLine());
		}

		int cnt = 0;

		for (int i = a - 1; i >= 0; i--) {
			while (b >= ary[i]) {
				if (b >= ary[i]) {
					cnt++;
					b -= ary[i];
				}
			}
		}
		System.out.println(cnt);
	}
}