[BJ] 백준 11047 동전 0 (JAVA)

문제

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

 

풀이 방법

대표적인 그리디 알고리즘 문제이다. 
동전의 단위가 있고, 금액이 있을 때 금액을 만들 수 있는 동전의 최소 개수를 구하면 된다.
순서는 정렬을 하고 단위가 큰 순서대로 금액에서 차감하면 되는데 입력값이 오름차순으로 주어진다고 했으니까 따로 정렬하지 않고 뒤에서부터 금액을 차감해주는 식으로 구현했다.
그리고 몫이 없으면 점점 단위가 내려가고 동전이 0이 되는 경우 for문을 벗어날 수 있게 해줬다.

 

제출 코드

import java.io.*;
public class BOJ_11047_동전0 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		int N = Integer.parseInt(str[0]);
		int K = Integer.parseInt(str[1]);
		int[] moneys = new int[N];
		for (int i = 0; i < N; i++) {
			moneys[i] = Integer.parseInt(br.readLine());
		}
		int ans =0; //동전 개수
		for (int i = N-1; i >=0;) { //마지막 부터 시작
			if(K/moneys[i] != 0) { //만약 몫이 있으면
				ans += K/moneys[i]; //동전 개수 추가
				K-= (K/moneys[i]) * moneys[i]; //몫*금액 만큼 K에서 빼기
			}else i--; //없으면 더 작은 단위로 
			if(K==0) break; 
		}
		System.out.println(ans);
	}
}