백준 동전 0(11047)

 

그리디 문제를 하나 풀어본다.

 

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

11047번: 동전 0

 

가장 간단한 그리디 알고리즘 문제이다 

현재 상황에서 최적의 상태를 체크해서 코인 개수를 구하고 나머지로 계속 반복하면 된다.

 

package greedy;

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

public class Q11047 {

    public static int answer = 0;

    public static void main(String[] args) throws IOException {
        greedy();
    }

    public static void greedy() 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[] coin = new int[n];

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

        for (int i=0; i < n; i++) {
            k = minus(coin[i], k);
        }
        System.out.println(answer);
    }

    public static int minus(int coin, int amount) {
        if (coin > amount) return amount;
        answer += amount / coin;
        return  amount % coin;
    }
}

 

결과