[C언어] 백준 5585 : 거스름돈

백준 5585 : 거스름돈

 

문제 링크

www.acmicpc.net/problem/5585

5585번: 거스름돈

 

 

문제 내용

잔돈으로 500엔, 100엔, 10엔, 5엔, 1엔이 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다.

잡화점에서 물건을 사고 1000엔을 냈을 때 받을 잔돈의 개수를 구하는 프로그램을 작성하시오.

단, 지불한 돈은 1 이상 1000 미만의 정수이다.

 

 

Idea

사용 알고리즘 : Greedy Algorithm ( 탐욕 알고리즘 )

 

제일 잔액이 큰 동전부터 사용하자!

1. money = 0 이면 종료
2. money보다 작거나 같은 coin을 찾는다.
3. money = money - coin
4. 1 ~ 3 반복

 

 

Code

#include <stdio.h>
 
int main() {
    int coin[] = { 500,100,50,10,5,1 };
    int money, i = 0, cnt = 0;
    scanf("%d", &money);
 
    money = 1000 - money;
    while (money != 0) {
        //동전이 거스름돈보다 클 때
        if (coin[i] > money) {
            i++;
            continue;
        }
        //동전이 거스름돈보다 작거나 같을 때
        else {
            money -= coin[i];
            cnt++;
        }
    }
    printf("%d\n", cnt);
    return 0;
}