(백준/C++) 11047_동전0

11047번: 동전 0 (acmicpc.net) 문제는 탐욕 알고리즘의 대표격인 문제로, 탐욕 알고리즘으로 풀 수 있는 문제입니다.

탐욕 알고리즘(Greedy Algorithm)이란, 매 순간 최적이라고 생각되는 방법을 선택하는 방식으로 문제를 해결하는 알고리즘입니다.

즉, 다른 경우의 수가 없이 현 문제에서 가장 좋아 보이는 것을 선택해 나가다보면 문제가 풀리는 알고리즘 입니다.

하지만, 탐욕 알고리즘이 항상 최적의 해를 찾을 수 있는 것은 아닙니다.

11047번: 동전 0 (acmicpc.net) 문제의 경우에는 다음 조건으로 인해 동전의 가치가 배수가 되기 때문에 가능한 문제입니다.

• i ≥ 2인 경우에 $A_i$는 $A_{i-1}$의 배수

---

접근법

탐욕 알고리즘은 매 순간 최선이라고 생각되는 방향으로 풀어나가면 됩니다.

이 동전 문제는 최대한 적은 동전을 사용하는 문제입니다. 따라서 가치가 높은 동전부터 사용하면 자연스럽게 적은 수의 동전을 사용할 수 있습니다.

---

풀이

합 K가 될 때까지 큰 동전부터 사용하는 코드를 작성하시면 됩니다.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int N, K, count = 0;
    cin >> N >> K;

    vector<int> coin(N);
    for (int i = N - 1; i >= 0; i--)
        cin >> coin[i];

    //가치가 큰 동전부터 계산한다.
    int remain = K;
    for (int i = 0; i < N; i++)
    {
        int quot = remain / coin[i];
        count += quot;
        remain -= coin[i] * quot;

        if (remain == 0) break;
    }

    cout << count;
}

---

추가

사실 모든 동전 문제가 탐욕으로 풀리는 것이 아닙니다.

예를 들어, 다음과 같은 동전 문제를 생각해봅시다.

• 동전의 종류: 1, 4, 6
• 목표 금액: 8

이 경우, 탐욕 알고리즘을 사용하면 6원 동전 1개와 1원 동전 2개를 사용하여 총 3개의 동전이 필요하게 됩니다.

하지만 실제로는 4원 동전 2개를 사용하면 2개의 동전만으로 8원을 만들 수 있습니다.

이렇게, 탐욕 알고리즘은 항상 최적의 해를 찾지는 못합니다. 조건을 보고 탐욕으로 풀릴 수 있는 문제를 잘 찾아내는 것이 중요합니다.