백준 11047번 :: 동전 0번 (그리디 알고리즘)

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

11047번: 동전 0

🎈 문제 풀이

 

현실 세계의 동전과 지폐의 가치는 작은 금액의 지폐의 몇 배수이다.

이 조건이 주어진 경우에, K 금액을 만족하는 동전의 최소수를 계산할 때

큰 동전부터 사용해야 한다.

예) 5만원, 1만원, 5천원, 1천원, 500원, 100원

165200원 = 5만원 + 5만원 + 1만원 + 5천원 + 100원 + 100원

모든 경우의 수를 계산해 볼 필요가 없다.

 

이 조건이 주어지지 않은, 동전 2 문제(2294번)의 경우에는 

큰 동전을 사용하지 않고 작은 동전을 사용하는 경우가 정답일 수도 있다.

예) 10원, 7원, 6원, 3원, 1원 동전이 주어졌을 때 19원이 목표 금액이라면

10원 + 7원 + 1원 + 1원 = 4개

10원 + 6원 + 3원 = 3개

7원을 건너 뛰고, 6원 동전을 사용하는 것이 정답이다.

모든 경우의 수를 계산해 보아야 한다.

 

🎈 소스 코드

 

public class Q11047_1 {
	
	static int[] arr;
	
	static int 최소수(int K) {
		int cnt = 0;
		for(int i=arr.length-1; i>=0; i--) { // 큰 동전부터 사용
			if(K == 0) break;
			if(arr[i] > K) continue;
			cnt += K / arr[i];
			K %= arr[i];
		}
		return cnt;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		arr= new int[N];
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		System.out.println(최소수(K));
	}
}

 

🎈 기억할 것

 

그리디 알고리즘 : 어떤 기준으로 항목을 하나씩 선택해 나가는 방식으로 최적의 해를 구하는 방식이다.