백준 문제풀이/그리디 알고리즘
백준 5585번 거스름돈 (python, c++)
minhui
2020. 6. 1. 00:00
5585번: 거스름돈
문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건�
www.acmicpc.net
거스름돈을 최소한 갯수의 동전으로 만들어야 하므로 가장 큰 동전부터 계산을 해야 한다.
가장 큰 동전을 먼저 나누고 몫은 즉 동전의 개수를 의미하므로 count변수에 더하고 다음 for문으로 가기 전에 나눠서 남은 돈을 저장하고 이 과정을 반복하여 최소 갯수를 구한다.
<python>
n=int(input())
m=1000-n
#500,100,50,10,5,1
arr=[500,100,50,10,5,1]
count=0
for i in arr:
if m < i :
continue
count += m // i
m = m % i
print(count)
* 연산자 /와 //의 차이는?
/ 는 나눗셈을 의미하며 결과가 float로 나타난다.
//도 역시 나눗셈을 의미하지만 결과가 int로 나타난다.
<C++>
#include <iostream>
using namespace std;
int main() {
int input, m;
int count = 0;
cin >> input;
m = 1000 - input;
int array[7] = { 500,100,50,10,5,1 };
for (int i = 0; i < 6; i++) {
if (m >= array[i]) {
count += m / array[i];
m %= array[i];
}
}
cout << count;
}