백준 - 14916

 

문제링크

문제요약

2원과 5원짜리 동전만 가지고있을때 거스름돈 n이 나오고 이 n에 만족하는 최소의 동전수를 구하는 문제

 

풀이

동전이 최소가 되기 위해서는 당연히 5원 위주로 거슬러 줘야한다.

 

5원 위주로 거슬러주려면 어떻게 해야할까 고민하다 그냥 5로 나눴을때 0일 될때까지 2를 뺐다.

 

그리고 거슬러 줄 수 없을때는 -1을 출력해야하는데 거슬러 줄 수 없는 경우는 낮은 숫자에서만 나타날꺼라고 생각하고 문제를 풀었다.

 

---

 

소스코드

#include <iostream>
using namespace std;

int n, ans;

int main() {
    cin >> n;
    while (n % 5 != 0) {
        n -= 2;
        ans++;
    }
    if (n == 0)
        cout << ans;
    else if (n < 0)
        cout << "-1";
    else 
        cout << ans + (n / 5);
}