[이코테/Python] 1장 그리디 - 거스름돈

문제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

 

 

문제의 기본 개념은 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이다.

 

exchange.c

#include <stdio.h>
int main(){
    int coin[4] = {500,100,50,10};
    
    int exchange;
    int count = 0;
    printf("put exchange: ");
    scanf("%d",&exchange);
    
    for(int i = 0;i < 4;i++){
        for(;1;){
            if(exchange < coin[0]){
                break;
            }
            else{
                exchange -= coin[0];
                count++;
            }
        }
        for(;1;){
            if(exchange < coin[1]){
                break;
            }
            else{
                exchange -= coin[1];
                count++;
            }
        }
        for(;1;){
            if(exchange < coin[2]){
                break;
            }
            else{
                exchange -= coin[2];
                count++;
            }
        }
        for(;1;){
            if(exchange < coin[3]){
                break;
            }
            else{
                exchange -= coin[3];
                count++;
            }
        }
        
    }
    
    printf("count is %d \n2",count);
    return 0;
}

 

exchange.py

n = 1260
count = 0
coin_type = [500, 100, 50, 10]

for coin in coin_type:
	count += n
    n %= coin
    
print(count)

확실히 파이썬 문법이 더 간결하고 확실하게 눈에 보인다.

 

이코테 저자의 cpp코드이다.

#include <bits/stdc++.h>

using namespace std;

int n = 1260;
int cnt = 0;
int coinTypes[4] = {500, 100, 50, 10};

int main() {
    for (int i = 0; i < 4; i++) {
        int coin = coinTypes[i];
        cnt += n / coin;
        n %= coin;
    }
    cout << cnt << '\n';
}

 

for문 연산에서 저 아이디어를 떠올리는게 코드를 더 간결하게 만들어주는 것 같다.