자바로 백준 11047 풀기

• 실버 1단계 문제

풀이)
동전의 종류는 10개이고, 각 동전의 개수는 제한이 없다.
동전을 이용해 합 K를 만들려 한다.
여기서 K는 1억 이하이며, int로 나타낼 수 있다.

대표적인 그리디 알고리즘이다. 현재 상태에서 최적의 선택을 해야 한다는 것.
주어진 선택지(동전 종류)에서 최적을 고르려면,
k 이하의 가장 큰 동전 가치를 선택하면 된다.
예를 들어 k = 4200 이면 맨 처음 선택지는 1000, 그다음은 500, 그다음은 100 ... 이런 식이다.

내 코드)

// 백준 온라인 저지 11047번

import java.io.*;
import java.util.*;

public class Main{
	public static void main(String[]args) throws IOException{
		
		// 입력. 
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int A[] = new int[N];
		for(int i=0;i<N;i++) {
			A[i] = Integer.parseInt(bf.readLine()); 
		}
		
		// 계산.
		int count = 0;
		for(int i=N-1;i>=0;i--) {
			count+=(K/A[i]);
			K %= A[i];
		}
		
		System.out.println(count);
	
	}
}