백준 11047(동전 0)

문제

---

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

 

 

 

 

풀이

---

탐욕알고리즘의 기초문제

동전 거스르기 문제랑 같은 문제라고 보면된다.

 

Greedy Algorithm 은 세가지 조건을 만족해야한다.

• 해 선택(Selection Procedure) : 지금 당시에 가장 최적인 해를 구한 뒤, 이를 부분해 집합에 추가한다.
• 적절성 검사(Feasibility Check) : 새로운 부분해 집합이 적절한지 검사한다.
• 해 검사(Solution Check) : 새로운 부분해 집합이 문제의 해가 되는지 검사한다. 아직 문제의 해가 완성되지 않았다면 1번부터 다시 시작한다.

이문제에서 최소개수를 구하려면 가장큰 수부터 비교를 해야한다.

Collections.sort( List, Comparator.resverseOrder()); 

함수를 이용해, 내림차순으로 동전들을 정렬한 뒤 문제를 풀었다

 

1. K수보다 동전이 크다면 돈을 맞출 수 없기에 넘어간다.
2. K 보다 수가 작다면 동전을 나누어 주어 개수를 더해준 뒤 나머지를 다시 K에 저장한다.
3. K 가 0이 될때 까지 위 1, 2 번을 반복한다.
4. K 가 0일때의 동전 개수를 출력한다.

위 방식을 통해서 문제를 풀었다.

 

 

<코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;


public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		String[] number = br.readLine().split("\\s");
		
		int n = Integer.parseInt(number[0]);
		int k = Integer.parseInt(number[1]);
		
		List<Integer> coin = new ArrayList<Integer>();
		
		for(int i = 0 ; i < n ; i++) {
			coin.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(coin, Comparator.reverseOrder());
		
		int count = 0;
		int i = 0;
		while(k > 0) {
			
			if(coin.get(i) > k) {
				i++;
				continue;
			}
			
			count += k / coin.get(i);
			k = k % coin.get(i);
			i++;
		}
		
		System.out.println(count);
	}
}