백준 11047번 동전 <S4>

그리디 알고리즘 중 하나로, 최소의 동전 개수로 해당하는 수를 만드는 문제이다.

높은 단위의 동전 값부터 뺼수 있다면 뺴고, 아니면 더 작은 값을 빼는 방식이면 될듯 싶다.

 

먼저 입력 받은 단위를 배열에 넣고(오름차순이므로 sorting은 필요없다)

for - while문을 통해서 뺄 수 있는지 여부를 판단하고 없다면 idx를 올려주었다. 빼게된다면 asnwer ++ 

import java.util.*;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        // Input
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int [] coin = new int[N];
        int answer = 0;
       
        for (int i = 0; i < N; i++) {
            coin[i] = sc.nextInt();            
        }
        sc.close();
 
        // Logic               
        for(int j = coin.length -1; j>=0; j--) {
            if(K >= coin[j]) {
                while(K >= coin[j]) {
                    K -= coin[j];
                    answer ++;
                }           
            }            
            if(K == 0) {
                break;
            }
        }        
        //output
        System.out.println(answer);
    }
}