백준 문제 : 동전 0 -11047

백준에서 제공해주는 Greedy algorithm 문제 동전 0이다.

 

문제 내용
- 준규가 가지고 있는 동전은 총 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의 배수)

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int coinCnt = sc.nextInt(); // 동전의 종류(N)
        int Sum = sc.nextInt(); // 그 가치의 합을 (K)
        int min = 0; //출력 값
        int temp = 0; //가치의 합과 비교하기 위한 temp
        int idx = 0;
        int[] coinType = new int[coinCnt]; //동전의 종류를 담기 위한 Array
        while(idx < coinCnt) { // 입력값을 Array를 넣기 위한 반복문
            coinType[idx] = sc.nextInt();
            idx++;
        }
        idx--;
        while (0 <= idx) { // 문제를 해결하기 위한 반복문
            if (temp == Sum) {
                break;
            } else if (temp < Sum) {
                while (temp + coinType[idx] <= Sum) {
                    temp += coinType[idx];
                    min++;
                }
            }
            idx--;
        }
        System.out.println(min);
    }
}