[JAVA] 백준 11047번 : 동전 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의 배수)

ㅇ 출력

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

ㅇ 링크

https://www.acmicpc.net/problem/11047

ㅇ 소스

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        long k = Long.parseLong(st.nextToken());

        int[] arr = new int[n];

        int startIdx = 0;

        for (int i = 0; i < n; i++) {

            int div = Integer.parseInt(br.readLine());

            arr[i] = div;

            if (k / div >= 1) {

                startIdx = i;

            }

        }

        int cnt = 0;

        for (int i = startIdx; i >= 0; i--) {

            cnt += k / arr[i];

            k -= (k / arr[i]) * arr[i];

        }

        System.out.println(cnt);

    }

}

ㅇ 해결방법 

 최소의 동전갯수를 구해야 하기 때문에 K를 나눌 수 있는 가장 큰 동전부터 카운트.