[Java] 백준 11047 동전 0

 

문제

n 종류의 동전이 주어진다.

동전을 적절히 사용해서 가치의 합을 K로 만드는 문제이다.

 

풀이

K보다 작은 동전의 가치중 가장 큰 값으로 K를 나눠 동전의 개수를 구하고

나머지로 K를 초기화한다.

K가 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 IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] coins = new int[N];
        for (int i = N - 1; i >= 0; i--) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        int idx = 0, cnt = 0;
        while(K > 0){
            while (coins[idx] > K) idx++;

            cnt += K / coins[idx];
            K %= coins[idx];
        }

        System.out.println(cnt);
    }
}