백준 11047 - 동전0

깃허브:

github.com/MSIQOC/BOJ/blob/master/b11047_%EB%8F%99%EC%A0%840.java

 

www.acmicpc.net/problem/11047

11047번: 동전 0

직관적으로 생각했을 때, K원을 만드는데 필요한 동전 개수의 최솟값을 구하려면 값이 큰 동전부터 사용해나가면 된다.

사용할 수 있는 값이 제일 큰 동전부터 사용하고 그 다음에 차례대로 큰 동전들을 사용하는 방식으로 문제를 풀었다.

//
//  Created by MinSeo on 2021/03/27.
//  Copyright ⓒ 2021 MinSeo Shin. All rights reserved.
//
import java.io.*;
import java.util.*;
public class b11047_동전0 {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int a[] = new int[n];
        for(int i=0; i<n; ++i) 
            a[i] = Integer.parseInt(br.readLine());
        int cnt=0;
        int j = n-1;
        while(k!=0) {
            if(k-a[j] >= 0) {
                k-=a[j];
                ++cnt;
            }
            else {
                --j;
            }
        }
        bw.write(cnt+"\n");
        bw.flush();
    }
}