[알고리즘] 백준 11047 동전 0 -그리디-

 

 

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

11047번: 동전 0

 

 

백준 단계별 풀기에서 그리디알고리즘 파트의 1단계를 풀어봤다.

문제를 푼 후 그리디 알고리즘 개념에 대해 살펴봤다.

 

[출처 : https://velog.io/@cyranocoding/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming%EA%B3%BC-%ED%83%90%EC%9A%95%EB%B2%95Greedy-Algorithm-3yjyoohia5]

Greedy Algorithms(탐욕법, 탐욕 알고리즘) Greedy Algorithm은 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다

 

 

 

 

 

풀이는 다음과 같이 했다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int moneyCount = sc.nextInt(); // 돈 종류 개수
        int totalMoney = sc.nextInt(); // 전체금액
        int result = 0; // 필요한 최소 동전개수
        ArrayList<Integer> moneyList = new ArrayList<>();

        for(int i=0; i<moneyCount; i++){
            moneyList.add(sc.nextInt());
        }

        Collections.sort(moneyList, Comparator.reverseOrder());

        for(int i=0; i<moneyCount; i++){
            int money = moneyList.get(i);
            result += totalMoney / money;
            totalMoney %= money;
        }

        System.out.println(result);
    }
}

 

Collections.sort 의 내림차순은 처음 써봤다. 까먹지 않도록 하자.

Collections.sort(moneyList, Comparator.reverseOrder());