[BOJ] 11047. 동전

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

11047번: 동전 0

---

접근 방법

그리디에 대한 기초 배낭 문제이다.

그리디는 현재 시점에서 최적의 해를 찾는 방법이며, 가장 최적의 해를 찾지 못할 수도 있다.

아직까지는 내가 무턱대고 작성한 코드를 그리디라고 이해하고 있다.

거스름돈을 주는 것처럼 가장 큰 금액부터 나누어 몫과 나머지를 구하는 것을 반복했다.

 

소스 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.valueOf(st.nextToken());
        int K = Integer.valueOf(st.nextToken());
        
        int min = 0;
        int[] coins = new int[N];
        for(int i=0; i<N; i++)
            coins[i] = Integer.valueOf(br.readLine());
        
        for (int i=N-1; i>=0; i--) {
            min += (K/coins[i]);
            K %= coins[i];
        }
        
        System.out.println(min);
    }
}