동전 문제( BOJ 1398 )

문제 : https://www.acmicpc.net/problem/1398

1398번: 동전 문제

 

문제 파악하기

주어진 초콜릿의 가격을 만들 수 있는 동전의 최소 개수를 구하는 문제입니다. 모든 동전이 우리나라 동전 체계처럼 약수 관계를 가지고 있다면 간단하게 사용할 수 있는 가장 큰 동전부터 사용하는 그리디 기법을 사용할 수 있습니다. 하지만 문제에 제시된 동전들은 약수 관계를 가지고 있지 않습니다. 이 경우에는 가치가 큰 동전부터 사용하는 것이 최적이 아닙니다. 예를 들어 초콜릿의 가격이 30원이라고 하면, 단순히 그리디 기법을 사용하면 [ 25원*1개 + 1원*5개 ]를 사용해야 한다는 결과를 얻게 됩니다. 하지만 실제로 30원을 만드는 최소의 동전 개수는 [ 10원*3개 ] 입니다. 따라서, 단순히 그리디 기법이 아닌 다른 방식이 필요합니다.

 

문제 해결하기

그렇다면 배열을 사용해서 우리가 원하는 금액까지 만들 수 있는 동전의 최솟값을 구해야할까요? 사실 입력되는 값의 크기가 작다면 모든 경우를 전부 구해도 됩니다. 하지만 이 문제에서는 최대 1015원 까지의 금액이 입력될 수 있다는 큰 문제점이 있습니다. 계산을 위해 이 금액만큼 배열을 만들기도 불가능할 뿐만 아니라, 만들어진 배열을 계산하는 데에도 1초라는 시간은 턱없이 부족합니다. 하지만 특정 범위만큼만 구할 수 있다면 어떨까요? 배열을 만들어서 계산해도 충분히 빠른 만큼의 구간을 정해서 구한 다음에, 모든 동전의 개수를 구할 때 사용하면 어떨까요?

 

문제에서 초점을 맞출 부분은 바로 25*100^k원 동전입니다. 우리가 사용할 수 있는 동전을 살펴보면 다음과 같습니다.

1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000 ...

 

동전을 자세히 보면 특징을 볼 수 있습니다. 바로, 25*100^k원을 기준으로 동전들이 일정 비율로 증가함을 확인할 수 있습니다. 

[ 1, 10, 25 ]*1, [ 1, 10, 25 ]*100, [ 1, 10, 25 ]*10000 ...

 

동전들은 항상 주기를 가지고 똑같은 방식으로 계산될 수 있으며, 모든 동전들은 [ 1, 10, 25 ]에서 100의 거듭제곱만큼 증가하기 때문에 일정 구간 내의 동전의 최소 개수는 항상 똑같습니다. 예를 들어, 30원을 만드는 동전의 최소 개수나 3000원을 만드는 동전의 최소 개수는 동일합니다. 10원 동전을 사용할 것인지, 1000원 동전을 사용할 것인지에 따른 차이점이지 사용하는 동전의 개수는 일정합니다. 따라서, 우리는 [ 1, 10, 25 ]로 만들 수 있는 1 ~ 99까지의 모든 값의 최소 동전 수를 구한 다음에, 이를 활용해서 문제를 해결할 수 있습니다.

 

방법은 간단합니다. [ 1, 10, 25 ]로 만들 수 있는 값은 최대 99까지의 두 자리 숫자입니다. 따라서, 우리는 두 자리씩 숫자를 끊어서 사용할 동전의 개수를 구한 다음, 사용된 동전의 총 개수를 구하면 됩니다. 예를 들어, 250111원을 만든다고 가정해봅시다.

250111원) 11원 만드는 방법 : [ 10원*1개 + 1원*1개 ] >> 2개

250100원) 100원 만드는 방법 : [100원*1개] >> 1개

250000원) 250000원 만드는 방법 : [250000*1개] >> 1개

 

모든 동전은 항상 [1, 10, 25]에서 100의 거듭제곱만큼 증가하는 비율을 가지고 있기에 우리는 항상 두 자리씩 끊어서 숫자를 만들게 되면 최소의 동전 개수를 만족할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <algorithm>
#define NMAX 100
#define lint long long int
using namespace std;
 
int T;
lint choco;
 
int ret;
int cnt[NMAX];
int coin[3] = {1, 10, 25};
 
void counting() {
    for(int i=1;i<NMAX;i++) cnt[i] = NMAX;
    
    for(int i=1;i<NMAX;i++) {
        for(int j=0;j<3;j++) {
            if(i-coin[j]<0) continue;
            
            cnt[i] = min( cnt[i], cnt[i-coin[j]]+1 );
        }
    }
}
 
int main() {
    // init
    counting();
    
    // solve
    scanf("%d", &T);
    while(T--) {
        scanf("%lld", &choco);
        
        ret = 0;
        while(choco) {
            ret += cnt[choco%100];
            choco /= 100;
        }
        
        printf("%d\n", ret);
    }
}
 
 

후기

재미있는 그리디 및 동적 프로그래밍 문제입니다. 아이디어가 중요한 문제이기에 해결했을 때의 기쁨도 더 큰 문제라고 생각합니다. 특정 알고리즘을 연습하는 사람보다는 생각하는 문제를 풀고 싶은 사람에게 소개하고 싶은 문제입니다.