[백준] 11047 동전0

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

11047번: 동전 0

 

기본적인 그리디 알고리즘 문제이다. Arrays.sort를 이용해 내림차순으로 정렬하려면 Collections.reverseOrder()이라는 메소드를 사용하면 되는데 기본적인 int 배열로는 활용이 불가능하다. 따라서 Integer 클래스 배열을 이용해 동전 값들을 받아서 사용했다.

---

문제 및 입출력

 

---

코드

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sum = sc.nextInt();
        int cnt = 0;
        Integer[] coin = new Integer[n];
        
        // n개의 동전을 입력받아 배열값 설정
        for(int i=0; i<n; i++)
        {
            coin[i] = sc.nextInt();
        }
        
        // 동전 값을 기준으로 내림차순 정렬
        Arrays.sort(coin, Collections.reverseOrder());
        
        // Greedy 알고리즘 적용(정렬된 동전 값 기준으로 개수 세기)
        for(int i=0; i<n; i++)
        {
            if((sum/coin[i])>0)
            {
                int temp = sum/coin[i];
                sum -= (coin[i])*temp;
                cnt += temp;
            }
        }
        
        System.out.println(cnt);
        sc.close();
    }
}