[11047번] 동전 0

이 문제에서는 1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수 라는 조건이 있으므로 탐욕법을 선택해도 반례가 존재하지 않는다.

✅ 탐욕법

탐욕법은 반례가 많이 있을 수 있다.
따라서, 반례가 없는지 생각해보고 없다면 택해야 하는 알고리즘이다.

✅ 코드

for-each문에 주의하자.

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

public class Main {

	static int arr[];

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

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

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

		arr = new int[n];

		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		int count = 0;

		for (int i = arr.length - 1; i >= 0; i--) {
			if (arr[i] <= k) {
				count += (k / arr[i]);
				k = k % arr[i];
			}
		}

		System.out.println(count);


	}
}