[백준] 11047 : 동전 0 JAVA 풀이

 

동전의 개수를 최소로 하는 방법은 가치가 큰 동전을 최대한 많이 사용하는 것이다.

 

1. 동전의 가치를 입력받고 ArrayList에 저장함

2. ArrayList를 동전의 가치가 큰 순서대로 정렬함

3. K가 0이 될 때까지 동전의 가치가 큰 것부터 거슬러주고 그 동전의 개수를 카운트함

 

 

import java.io.*;
import java.util.*;

public class Main {

	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());
		
		ArrayList<Integer> list = new ArrayList<>();
		
		for(int i=0;i<N;i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		
		list.sort((o1, o2)->{
			return o2-o1;
		});
		
		int cnt = 0;
		int idx = 0;
		
		while(K!=0) {
			if(list.get(idx)>K) {
				idx++;
				continue;
			}
			cnt += K/list.get(idx); // 동전의 개수 추가
			K %= list.get(idx); // 거슬러주고 남은 돈으로 업데이트
		}
		System.out.println(cnt);
	}

}