[백준/c++] 14916번: 거스름돈

 

 

https://www.acmicpc.net/problem/14916

14916번: 거스름돈

 

2원, 5원을 사용해서 거스름돈을 줘야 하는데, 5원을 먼저 나누고 나머지를 2로 나누면 되는가? 아니다

N=13의 경우, 5원 2개 / 2원 1개 이렇게 하면 안 된다. 대신 5원 1개 / 2원 4개로 하면 된다.

즉, 5원이 0개 / 1개 / 2개 사용하는 경우를 모두 확인해봐야 최적의 해를 구할 수 있다. 

 

그러므로 N을 5원으로 나눠서 5원을 최대로 많이 사용할 수 있는 경우를 u에 넣어주고

for문을 사용해서 최솟값을 구하면 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, cnt=2147483647;
    cin >> n;
    
    int u = n / 5;
    for(int i=0; i<=u; i++){ //5원을 0개부터 u개 사용하는 경우
        int m = n, c = i;
        m -= 5 * i;
        c += m / 2;
        m %= 2;
        if(m == 0){
            cnt = min(cnt, c);
        }
    }
    if(cnt == 2147483647) cout << "-1\n";
    else                  cout << cnt << '\n';
    return 0;
}