백준 그리디 알고리즘 - 동전 문제 11047번(JAVA)

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

package greedy;
 
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Scanner;
 
import javax.sound.sampled.ReverbType;
 
/*
 * 문제 
 * 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
 * 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
 * 
 * 입력
 * 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
 * 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
 * 
 * 출력
 * 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
 * 
 * */
 
public class Coin {
 
    //오름차순 정렬 메소드
    public static int[] reverseArray(int[] kindsOfCoins) {
 
        for (int i = 0; i < kindsOfCoins.length - 1; i++) {
            for (int j = i + 1; j < kindsOfCoins.length; j++) {
                if (kindsOfCoins[i] < kindsOfCoins[j]) {
                    int temp = kindsOfCoins[j];
                    kindsOfCoins[j] = kindsOfCoins[i];
                    kindsOfCoins[i] = temp;
                }
            }
        }
//        System.out.println(Arrays.toString(kindsOfCoins));
        return kindsOfCoins;
    }
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        // 동전의 종류(n)
        int kind = sc.nextInt();
 
        // 금액(k)
        int amount = sc.nextInt();
 
        // 동전의 금액을 넣을 배열, 입력할 동전의 종류만큼 kindsOfCoins배열의 크기를 설정한다.
        int[] kindsOfCoins = new int[kind];
 
        // 동전의 갯수
        int sumQuotient = 0;
 
        // 배열에 동전의 종류를 입력한다.
        for (int i = 0; i < kind; i++) {
 
            kindsOfCoins[i] = sc.nextInt();
 
        }
 
        kindsOfCoins = reverseArray(kindsOfCoins);
        //정렬된 배열 출력
//        System.out.println(Arrays.toString(kindsOfCoins));
 
        for (int i = 0; i < kind; i++) {
 
            if (amount / kindsOfCoins[i] > 0) {
 
                int quotient = amount / kindsOfCoins[i];
                amount = amount % kindsOfCoins[i];
                sumQuotient += quotient;
//                System.out.println("sumQuotient : " + sumQuotient);
//                System.out.println("amount : " + amount);
            }
 
        }
 
        System.out.println(sumQuotient);
 
    }
 
}