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

동전 0 문제

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

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

그리디 알고리즘

그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만 고르는 것'이다. 따라서 항상 최적의 결과를 도출하지 않아 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 정당성 분석이 중요하다.

기본적으로 무조건 큰 경우대로, 무조간 작은 경우대로 등 극단적으로 문제에 접근한다는 점에서 정렬 기법이 함께 사용되는 경우가 많다.

---

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 동전 종류
        int M = sc.nextInt(); // 목표 금액
        int[] arr = new int[N];

        for(int i = 0 ; i < N ; i++){
            arr[i] = sc.nextInt();
        }
        
        int cnt = 0; // 동전의 개수를 세는 변수

        for(int i = N - 1; i >= 0; i--){ // 오름차순 정렬이 되어있으니 뒤에서부터 시작
            if(arr[i] <= M){ 
                cnt += M / arr[i];
                M %= arr[i];
            }
        }

        System.out.println(cnt);
    }
}

추가 내용

대표적인 그리디 알고리즘 문제로는 거스름 돈 문제가 있다.
일반적으로 그리디 알고리즘을 통해 거스름 돈 문제를 풀 때에 보통 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장한다.
가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

만약 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원일 때 가장 큰 단위를 우선할 시 500원 1개, 100원 3개가 나와서 4개를 사용하지만 400원 2개만으로 거스름 돈을 줄 수 있다. (500원이 400의 배수가 아니기 때문에 이러한 문제가 발생)
이처럼 그리디 알고리즘은 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다.