[백준] 5585.cpp : 거스름돈

www.acmicpc.net/problem/5585

5585번: 거스름돈

#include <iostream>
int main(void)
{
  int n, i = 0, res = 0;
  int bills[6] = {500, 100, 50, 10, 5, 1};
  std::cin >> n;
  n = 1000 - n;
  // 거스름돈이 0원이 될 때 까지
  while(n != 0)
  {
    // 만약 이번 단위로 빼는게 가능하다면
    if(n - bills[i] >= 0)
    {
      // 빼주고 카운트 해줌
      n -= bills[i];
      res++;
    }
    // 빼는게 불가능하다면 다음 작은 단위로
    else
    {
      i++;
    }
  }
  std::cout << res << '\n';
}

 

[Try]

1. 큰것부터 차근차근 최대한 많이 빼준다. 그리디알고리즘

 

[Point]

1. 그냥 몫으로 구해도 되었을 것을... 괜히 복잡하게 만들었다 ㅋㅋ

2. 저렇게 빼주는 행위 자체가 나누는 연산자를 풀어놓은거라는 걸 생각하지 못했다 아쉽