[알고리즘_풀이] 백준 11047번 동전0, Greedy

DP가 아닌 Greedy를 떠올려야 하는 이유

 

 

Ai는 Ai-1의 배수이므로, 모든 경우의 수를 전부 다 해보는 dp로 한다면, 비효율적이다. 따라서 그리디로 구현해야한다.

 

 

코드

package greedy;

import java.util.Scanner;

// 문제 : 동전 0
// 예제1 : 동전 10(N)종류로 4200(K)원을 만들 때, 동전개수의 최솟값구하기
public class backjoon_11047 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 1. 입력
        int N = sc.nextInt(); // N : 동전종류의 수
        int K = sc.nextInt(); // K : 동전의 합

        //동전의 수(N)만큼 입력받기
        int[] coins = new int[N];
        for(int i=0; i<coins.length; i++){
            coins[i] = sc.nextInt();
        }

        // 동전의 수를 counting
        int count = 0;

        // 2. while문으로 동전이 큰것부터 작은순으로 반복하여, 다음을 수행한다.
        //    -> while() {
        //         if(동전[i] > 동전의 합) continue;
        //         (동전의 합) = (동전의 함) - (해당 동전)
        //         가짓수 하나 늘리기
        //    }

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

            K -= coins[i];
            count += 1;
        }

        // 3. count 출력
        System.out.println(count);

    }
}