(C++) - 백준(BOJ)코딩 11047번 : 동전0

www.acmicpc.net/problem/11047

11047번: 동전 0

greedy 문제였습니다.

 

greedy로 푸는 것이 수학적으로 맞는지를 검증하는지가 중요합니다. 감으로 의존해 푸시면 제대로 문제를 풀 수 없습니다. 좋은 방법 중 하나는 귀류법으로 자신이 세운 가정이 맞는지를 증명해보는 것입니다. 귀류법을 통해 현재 최대 이익을 얻지 않으면 발생되는 손해가 있는지의 여부를 알 수 있습니다.

 

 

풀이방법

귀류법으로 증명 : 귀류법 명제가 거짓이라고 가정 할 때 모순이 생긴다는 점을 보임으로써 해당 명제가 참임을 증명함
명제 : 가장 높은 가치의 동전으로 최대한 많이 사용하면 필요한 동전은 최소이다.
보조정리 1. 쓰는 동전 최소로 하려면 10,100원 동전은 각각 4개 이하, 50원 동전은 1개 이하로 사용해야 한다.
보조정리 먼저 증명 -> 보조정리1이 거짓이라면 쓰는 동전 최소로 하려면 10,100원 동전은 5개 이상 사용해야 한다라는 가정이 참이 되어야 합니다.
10원 5개는 50원 1개로 대체 가능하고 100원 5개는 500원 짜리 동전 1개로 대체될 수 있습니다. 따라서 대체 후 사용한 동전의 개수가 더 적으므로 모순이 발생합니다.
이 방식으로 명제 1이 거짓일 경우에는 : 작은 가치의 동전으로 최대한 많이 사용하면 필요한 동전은 최소이다.를 가정했을 때 앞의 보조정리1의 예시로

10,50,100원 동전으로는 물건값을 최대 10x4 + 50 x 1 + 100 x 4 = 490원까지만 표현할 수 있습니다. 
500원을 사용하지 않을 경우엔 500원 이상을 10,50,100원 짜리로 500원 이상을 갑당해야합니다.
그러므로 500원을 사용하지 않으면 최소로 표현될 수 없으므로 500원을 사용해야 합니다. 모순이 발생하므로 명제는 참입니다.
이렇게 동전의 최대값을 현재 가지고 있는 동전의 가치가 가장 큰 것부터 차례대로 설정하고 조금씩 낮춰가면서 귀류법으로 증명해가면 해당 참인지 알 수 있습니다.

 

하지만 이렇게 배수관계로 있는 동전 종류에 대해서는 다음과 같은 증명이 가능하지만 배수관계가 아닌 동전에 대해서는 반례가 존재합니다.

 

1,9,10원 짜리 동전으로 18원을 만들어 볼 때

기존 방법으로는 10원짜리 1개, 1원짜리 8개 총 9개의 동전을 사용하게 됩니다.

하지만 실제 답은 9월짜리 2개를 사용하는 것입니다.

 

따라서 이럴 때는 다른 명제를 세워 증명해야합니다. 이렇게 사소한 조건의 변화만으로도 풀이가 확 달라질 수 있어서 조심을 해야하고, 비슷해보이는 문제를 풀어봤다는 이유만으로 풀이의 방향을 한정짓는건 굉장히 위험할 수 있습니다.

 

Code

#include <iostream>
using namespace std;
int n, k;
int coin[10];
int sum;
int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> coin[i];
    for(int i = n-1; i >= 0; i--){
        sum += k / coin[i];
        k %= coin[i];
    }
    cout << sum << '\n';
}

 

 

*증명방식은 해당 블로그를 참조했습니다.

 

blog.encrypted.gg/975?category=773649