[백준] 11047 - 동전 0

[문제링크]

11047번: 동전 0

 

0. 최소한의 갯수로 목표 금액을 맞추는 문제

 

1. 모든 고액권은 소액권의 n배수로 떨어지므로, 항상 가장 큰 액수부터 선택하는게 유리하다

• 그리디 알고리즘

 

2. 목표 금액을 초과하지 않는 선에서, 가능한 많은 금액을 고액권부터 채워나간다

 

3. 목표 금액이 완성되면, 최종 갯수를 출력

 

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int k = pint(st.nextToken());
		
		int[]money = new int[n];
		for (int i = 0; i < n; i++) {
			money[i]=pint(br.readLine());
		}
		int cnt=0, idx=n-1;
		while(k!=0) {
			cnt+=k/money[idx];
			k%=money[idx--];
		}
		System.out.println(cnt);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과화면