[백준 BOJ] 5585 거스름돈

[백준 BOJ] 5585 거스름돈

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다..

문제로 이동할려면 여기를 클릭하세요.

풀이

  • 1000원에서 입력된 돈을 빼주어 거스름돈을 구합니다.
  • 거스름돈에서 잔돈이 제일 큰 500부터 나눠줍니다.
    • 500보다 작아 몫이 0이면 그 다음 작은 100원으로 잔돈을 줄여줍니다.
  • 위를 반복하다 나머지가 0이 되면 남은 거스름돈이 없으므로 반복문을 탈출해줍니다.

예제

1
2
3
4
5
6
7
8
9
10
11
12
13

입력 : 380
거스름돈 : 1000 - 380 = 620

반복문
- 620 / 500 = 1
  620 % 500 = 120
- 120 / 500 = 0
- 120 / 100 = 1
  120 % 100 = 20
- 20 / 100 = 0
- 20 / 50 = 0
- 20 / 10 = 2
  20 % 10 = 0

코드

#include <iostream>
using namespace std;
int main() {
int money;
cin>>money;
money = 1000 - money;
int change[6] = {500, 100, 50, 10, 5, 1};
int quotient = 1;
int cnt = 0;
int i = 0;
while(1){
quotient = money/change[i];
cnt = cnt + quotient;
if(quotient == 0){
i++;
continue;
}
money = money%change[i];
if(money==0) break;
}
cout<<cnt;
return 0;
}
view raw 5585_거스름돈.c++ hosted with ❤ by GitHub