[코드트리] Greedy - 그리디 알고리즘 / 동전 연습문제

 

1, 4, 5 동전을 이용하여 8원을 거슬러주기 위해
필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요.

 

위 문제를 보면 당연히 큰 동전부터 쓰는 것이 좋아 보입니다.

하지만 큰 동전부터 사용하게 되면 5 + 1 + 1 + 1이므로 4개의 동전이 필요하지만,
4 + 4 역시 8 이므로 최소 동전의 수는 2가 됩니다.

 

그런데 다음 경우는 어떨까요?

 

1, 5, 10, 20 동전을 이용하여 78원을 거슬러주기 위해
필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요.

 

이 경우에는 큰 동전부터 거슬러주는 것이 항상 좋습니다.

그 이유는 주어진 동전들이 전부 배수관계에 놓여있기 때문입니다. 

그렇기에 큰 동전이 사용이 가능하다면, 작은 동전을 사용하는 것보다 항상 좋은 선택이 되는 것입니다.

 

따라서 배수 관계에 놓여있는 동전이 주어졌을 때에는, 항상 큰 동전부터 이용하는 것이 좋음을 알 수 있습니다.

 

이처럼 현재 상황에서 최선이다 싶은 것을 계속 반복하는 알고리즘을 그리디 알고리즘, 욕심쟁이 기법이라 부릅니다.

이러한 greedy 알고리즘이 주어진 동전끼리 배수관계에 놓여있는 문제에서는 실제 최적의 답을 가져와주게 됩니다.

greedy 알고리즘은 비록 많은 문제에 대해 최적의 답을 가져와 주지는 못하지만, 그 방법이 굉장히 간단하기 때문에 최적의 답을 구하기 힘든 복잡한 문제에 대해 실제 답에 근사한 결과를 빠르고 간결하게 구하고 싶을 때 자주 사용되기도 합니다.

 

---

 

연습문제 : 동전 더하기

서로 다른 동전 n 종류로 금액 k를 완성시키기 위해 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하세요.

단, 2번째부터 주어지는 동전의 가치값은 항상 바로 전 동전의 가치의 배수로 주어집니다.

입력 형식

첫 번째 줄에 동전의 종류 개수 n과 금액 k가 공백을 사이에 두고 주어집니다.

두 번째 줄부터 n개의 줄에 걸쳐 각 동전의 가치가 작은 동전부터 큰 동전까지 순서대로 주어집니다.

• 1 ≤ n ≤ 10
• 1 ≤ k ≤ 100,000,000
• 1 ≤ 동전의 가치 ≤ 1,000,000

단, 주어진 동전들로 k원을 만들지 못하는 입력은 주어지지 않습니다.

출력 형식

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

---

나의 풀이

#include <iostream>
using namespace std;
int main() {
    int n; int k;
    int coin[11]={0,};
    cin >> n >> k;
    for(int i=0; i<n; ++i) cin >> coin[i];
    int cnt=0; int i=1;
    while(k!=0){
        if(k >= coin[n-i]) {
            k-=coin[n-i];
            cnt ++;
        }
        else i++;
    }
    cout << cnt;
    return 0;
}

 

현재 상황에서 최선인 것을 반복하는 욕심쟁이!

근데 동전 문제에서의 욕심쟁이 기법 조건은 오늘 처음 알았다

배수 관계 기억하기