백준 11047: 동전 0(java)

문제

---

풀이

 

동전의 개수가 최소가 되려면, 가치가 큰 동전이 최대한 많이 포함되어야 한다.

 

입력받은 동전의 가치가 K보다 클 경우 사용할 수 없으므로, 가치가 K 이하인 동전들만 염두에 두고 풀이한다.

List<Integer> list=new ArrayList<>();
for(int i=0; i<N; i++) {
	int input=Integer.parseInt(br.readLine());
			
	if(input<=K) {
		list.add(input);
	}
}

고려할 동전의 개수를 알지 못해 가변적 크기의 컨테이너가 필요해 배열이 아닌 컬렉션을 사용한다. 이후 Collections.sort()를 이용해 동전들을 정렬해야 하므로 List형 컬렉션 list를 선언했다.

Collections.sort(list);

int count=0;
for(int i=list.size()-1; i>=0; i--) {
	int num=list.get(i);
			
	count+=K/num;
	K%=num;
}

list를 오름차순으로 정렬하고, 값이 가장 큰 동전부터 나누며 계산하면 된다.

Collections.sort(list, Collections.reverseOrder());로 내림차순 정렬한 후, for문 순서를 반대로 해 풀이해도 무방하다.

 

전체 코드

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

public class ex11047 {

	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());
		
		List<Integer> list=new ArrayList<>();
		for(int i=0; i<N; i++) {
			int input=Integer.parseInt(br.readLine());
			
			if(input<=K) {
				list.add(input);
			}
		}
		
		Collections.sort(list);
		
		int count=0;
		for(int i=list.size()-1; i>=0; i--) {
			int num=list.get(i);
			
			count+=K/num;
			K%=num;
		}
		
		System.out.println(count);
	}
}