● 백준/그리디(Greddy)
[백준] 백준 5585번 거스름돈(그리디 알고리즘)
user...
2020. 6. 29. 15:55
문제
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한 장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include <stdio.h>
#include <stdlib.h>
int main(){
int num;
int count = 0;
scanf("%d", &num);
num = 1000-num;
count += num / 500;
num %= 500;
count += num / 100;
num %= 100;
count += num / 50;
num %= 50;
count += num / 10;
num %= 10;
count += num / 5;
num %= 5;
count += num;
printf("%d", count);
}
|
cs |
해설
정말 쉬운 문제이다. 돈 물건값을 내준 잔돈에 대하여 그리디 알고리즘을 적용하면 된다.
문제 출처 : 백준