[백준] 11047번 : 동전 0 - JAVA [자바]

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

그리디 알고리즘 문제이다.

1. 동전의 가격들을 배열에 입력 받는다.
2. 배열의 가장 뒤에서부터 K 를 나눌 수 있는지 보고, 나눌 수 있다면 K의 값과 동전의 갯수를 업데이트한다.
3. 모든 동전의 값으로 탐색한 뒤 총 동전의 갯수를 출력한다.

public class bj11047 {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] split = br.readLine().split(" ");
        int N = Integer.parseInt(split[0]);
        int K = Integer.parseInt(split[1]);
        int[] cost = new int[N];

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

        int answer = 0;
        for (int i = N - 1; i > -1; i--) {
            answer += K / cost[i];
            K %= cost[i];
        }

        bw.write(answer + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}