[백준] 14916번 거스름돈 C++ 코드

코드

#include <iostream>

using namespace std;
const int INF = 987654321;
int n, a[100003],res = INF;
int main() {
  cin >> n;
  int div = n / 5;
  int tempdiv = div;
  while(tempdiv != -1) {
    int mo = n%5 + 5*(div - tempdiv);
    if(mo%2 == 0) {
      int temp = tempdiv + mo/2;
      res = min(res, temp);
      break;
    }
    tempdiv--;
  }
  if(res == INF) res = -1;
  cout << res << '\n';
  return 0;
}

그리디 방식으로 해결할 수 있을 것 같아서 시도했다. 5로 나눈 몫을 1개씩 줄여가며 동전 개수를 구했다. 이러면 차라리 2를 계속 빼서 5의 배수를 구하는 것도 괜찮았을 거라는 생각이 든다.