[java, 알고리즘, 그리디] :: 백준 - 동전 0

2021/02/17 - [Programming/Java] - [java, 알고리즘, 그리디] :: 백준 - ATM

---

 

www.acmicpc.net/problem/11047

11047번: 동전 0

package com.algorithm.greedyEx05;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class GreedyEx05 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int kinds = Integer.parseInt(st.nextToken());
        int amount = Integer.parseInt(st.nextToken());
        int num [] = new int[kinds];

        for(int i = 0; i < kinds; i++){
            num[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(num);

        int cnt = 0;
        int tmp = amount;
        for(int i = kinds - 1; i >= 0; i--){
            if(tmp % num[i] < amount){
                cnt += tmp / num[i];
                tmp %= num[i];
            }
        }
        System.out.println(cnt);
    }
}

 

접근 방법

동전의 종류 중에 총금액보다 작으면서 가장 큰 수부터