오늘의 코드. 14일차 (백준/11047번 동전 0)

 

이번에 해외여행을 일본으로 다녀오느라 포스팅이 불규칙적이었다.
일본여행 중 굉장히 동전을 많이 가지고 있게 되었는데, 귀국할때 최대한 동전을 적게 들고오기 위해 계산을 했던 기억이 난다. 그때의 기억을 떠올려보며 글을 써보려 한다.

 

Baekjoon / Problem No. 11047 (동전 0)

 

Problem

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

Input

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

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

Output

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

---

Solution

동전의 개수를 최소로 하면서 일정 금액을 만드는 문제이다.

 

돈의 특징으로 100원 5개가 500원 1개로 대체될 수 있다라는 점을 생각해보자.

동전의 개수를 최소화 해야하기 때문에 당연히 더 높은 금액권으로 지불할 수 있다면 그렇게 하는 편이 유리하다.

 

이런식으로 고액권 부터 차례로 (위에서 서술한)유리한 상황을 순간 순간 이어나갈 수 있다면?

결과적으로 유리한 상황이 계속 유지될 것이므로, 최적의 답을 찾을 수 있을 것이다.

 

바로 이것이 그리디 알고리즘을 (쉽게) 설명한 것이라고 생각하면 된다.

그리디 알고리즘(Greedy Algorithm)은 '탐욕 알고리즘'이라는 뜻으로, 그 순간 순간 최적이라 생각하는 방향을 계속 따라가면 최선의 결과가 나올것이라 생각하는 알고리즘이다.

 

이 문제의 경우 심지어 더 편하게 동전의 가치를 순서대로 제시하고 있으므로, K를 고액권부터 차례로 나눠가면서 나눠진 수만큼 카운팅하여 출력만 하면 될 것이다.

---

Code

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

int main()
{
    int N, K;
    int count = 0;
    vector<int> cost;

    scanf("%d %d", &N, &K);

    for (int i = 0; i < N; i++)
    {
        int c;
        scanf("%d", &c);
        cost.push_back(c);
    }

    for (int j = N - 1; j >= 0; j--)
    {
        count += (K / cost[j]); // 동전을 사용한 횟수
        K = K % cost[j]; 
    }

    printf("%d", count);

    return 0;
}

 

---

Review

간단한 일종의 그리디 알고리즘을 통해 문제를 해결해 보았다.

 

그리디 알고리즘은 위에서 설명하였듯이, 항상 최선의 선택을 한다면, 결국 최선의 결과가 나올 것이라고 본다.

어찌보면 역설적이게도 그리디 알고리즘 그 자체도 역시 최선이 아니다. 

그 순간 순간에 최선의 선택을 한다고 해도 그것이 최선의 결과로 이어질지는 미지수이기 때문이다.

 

우리도 그렇다. 매 순간 순간 행복하기위해 이것저것 선택하고 결정해도 그것이 진정 그 끝에서 최선의 길인지 사실은 누구도 모른다.

 

최선의 결과는 어디에서 보나 최선이라고 볼 수 없다.

그것도 엄청난 수의 사람들이 살아가는 이 세상이 돌아가는 알고리즘(이 있을지는 모르겠다.)속에서는

무엇이 최선의 선택인지조차 알 수 없다.

 

우리는 주로 위인들의 시련과 그것을 멋지게 극복해내는 스토리에 열광하곤 한다.

항상 완벽할 필요는 없다. 그것이 진정한 완벽인지는 그 끝에 가서야 알수 있으니까.

 

사설이 길었다.

여행과 개인적인 사정으로 며칠동안 오늘의 코드를 조금 쉬게 되었다. 더 나은 포스트를 위한 투자로 봐준다면 감사하겠다.