11047: 동전 0(백준)

 

 

문제 해결 과정)

풀이 과정은 간당하게 큰 단위부터 우선 지급한 다음에 남은 돈은 그다음 작은 화폐로 지급하면 최소 사용 동전의 개수를 구할 수 있습니다.

#include <stdio.h>

void Charges(int* price, int sum, int num){
    
    int count=0;
    int total = sum;
    
    for(int i=num-1; i>=0;i--){
        count += (total/price[i]);
        total = total % price[i];
    }
    
    printf("%d",count);
}

int main(){
    
    int coin[10]={0,};
    int money;
    int count;
    
    scanf("%d %d",&count, &money);
    for(int i=0;i<count;i++)
        scanf("%d",&coin[i]);
    
    Charges(coin, money, count);
    
}

 

여기서 큰 단위의 화폐를 먼저 지급하고 남는 나머지를 그다음 화폐로 지급해도 최소로 동전을 사용한다고 보장할 수 있는 이유는 문제에서 "큰 단위의 화폐는 반드시 작은 화폐단위의 배수다."라는 조건을 설정하였기 때문입니다.

 

예를 들어 500,400,200원 동전으로 800원을 만들되 가장 최소한의 동전을 사용해야 한다고 하면, 400원 동전 2개를 사용해야 되는데, 500원은 200원의 배수가 아니기에 이러한 예외 사항이 발생하는 것입니다.

 

문제에서는 큰 단위 화폐는 작은 단위 화폐의 배수라는 조건을 설정하였기 때문에 예외사항 없이 간단하게 구현할 수 있습니다.