[BAEKJOON] 11047번 동전 0

---

정해진 동전의 가치로 주어진 금액을 만들 수 있는 경우의 수 중 동전을 최소한으로 사용한 경우를 찾아야 한다.

주어진 금액과 동전의 가치가 같거나 작은 것으로 구성될 것이다.

동전의 가치가 높은 것부터 차례대로 주어진 금액과 비교한다.

현재 금액을 몇 개의 동전으로 만들 수 있는지 찾는다.

현재 금액을 동전의 가치로 나눈 몫이 동전의 개수일 것이다.

이때 동전의 개수는 반복문을 빠져나올 때까지 계속해서 누적시킨다.

다음 비교할 동전을 위해 현재 금액에서 이전 동전으로 만들 수 있는 금액을 빼준다.

가치가 낮은 동전을 사용할 때까지 반복하면 누적 동전 개수를 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int price = Integer.parseInt(st.nextToken());
		int arr[] = new int[N];
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		for (int i = N - 1; i >= 0; i--) {
			if (arr[i] <= price) {
					cnt += (price/arr[i]);
			}
			price -= arr[i]*(price/arr[i]);
		}		
		System.out.println(cnt);
	}
}

[출처]

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

11047번: 동전 0