11047번 동전0

문제 링크 : www.acmicpc.net/problem/11047

11047번: 동전 0

<<알고리즘>>

1. 입력받은 단위를 오름차순 / 내림차순 순으로 정렬

2. 제일 큰 가치의 동전부터 목표치에서 빼나간다. 이때 동전의 갯수 증가

3. 동전의 개수 출력

 

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

public class Main{
	public static void main(String[] args) {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String s = "";
		try {
			s = bf.readLine();
		}catch(IOException e) {}
		StringTokenizer st = new StringTokenizer(s);
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int money[] = new int[N];
		for(int i =0;i<N;i++) {
			try {
				s = bf.readLine();
			}catch(IOException e) {}
			money[i] = Integer.parseInt(s);
		}
		Arrays.sort(money);
		
		int count =0;
		for(int i =N-1;i>=0;i--) {
			while(true) {
				if(K>=money[i]) {
					++count;
					K-=money[i];
				}
				else {
					break;
				}
			}
		}
		System.out.println(count);
	}
}