[백준] 11047. 동전0

문제 출처: www.acmicpc.net/problem/11047

11047번: 동전 0

: 동전의 종류 N과 가치의 합 K와 각각의 동전들이 오름차순으로 주어진다.

: 이때, 각각의 동전들은 서로 배수의 관계를 가지고 있기 때문에 그리디 알고리즘으로 풀 수 있댜.

: 큰 수부터 가치의 합 K를 나눴을 때의 몫을 count해주면 된다.

: 그러면 자동으로 가치가 큰 동전을 사용해서 가치의 합을 만들 수 있고, 그 동전의 개수는 최소가 된다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	
	public static void main(String[] args) throws IOException {
		// 동전의 종류 N과 동전 가치의 합 K를 입력받음
		st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[] coins = new int[N];
		// N개의 동전을 오름차순으로 입력받음
		for(int i = 0; i < N; i++)
			coins[i] = Integer.parseInt(br.readLine());
		
		int cnt = 0;
		// 금액이 큰 순서대로 나눈 몫을 count에 더해주기
		for(int i = N-1; i >= 0; i--) {
			cnt += K/coins[i];
			K %= coins[i];
		}
		System.out.println(cnt);
	}
}