[11047번] 동전 0

문제 기출 : [https://www.acmicpc.net/problem/11047]

 

 

풀이 방법

[그리디 알고리즘] 접근   K원을 민드는데 필요 동전의 개수의 최소값은 동전의 가치가 큰 녀석부터 선택해가면서 차감시킨다. 물론K보다 같거나 작은지 체크 해가면서.   문제에서 친절하게도 오름차순으로 준다. sort가 필요 없다는 말이다. 나는 읽은 동전의 가치가 K보다 같거나 크면 더 이상 읽지 않는다. 무의미하기 때문이다. 어차피 사용하지 못하는 동전이기 때문이다.   그럼 읽은 동전의 가치 중에서 가장 가치가 높은 순서대로 선택해서 K가 0 이하가 될 때까지 K원에서 차감시킨다.

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		int answer = 0;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
		try {
			int N = Integer.parseInt(br.readLine());
			int K = Integer.parseInt(br.readLine());
			int[] money = new int[N];

			for (int i = 0; i < N; i++) {
				money[i] = Integer.parseInt(br.readLine());

				if (money[i] >= K) {
					break;
				}
			}

			int i = money.length - 1;
			while (K >= 0) {
				if (i < 0) {
					break;
				}
				if (money[i] == 0) {
					i--;
					continue;
				}

				if (K >= money[i]) {
					K -= money[i];
					answer++;
				} else {
					i--;
				}
			}

			System.out.println(answer);
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}