[Algorithm]Baekjoon 14916 :: 거스름돈

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

14916번: 거스름돈

 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
 
    cin >> n;
 
    if (n == 1 || n == 3)
    {
        cout << -1;
        return 0;
 
    }
 
    int answer = 0;
    int a = n % 5;
    int b = n / 5;
 
    if (a % 2 != 0) --b;
 
    answer += b;
 
    n -= 5 * b;
 
    answer += n / 2;
    cout << answer;
}
 
 
 

 

dp 카테고리에 있어서 풀려고 봤는데, 그런거 할필요없이 간단하게 풀 수 있는 문제.

사용할 수 있는 도전이 2원,5원밖에 없는데 이걸로 최소의 동전개수로 거슬러줘야 한다.

그냥 5원짜리로 최대한 금액을 뺀다음에, 해당금액이 홀수일경우 2원짜리로 처리못하니까 5원짜리 하나 빼주고 다시 2원짜리로 처리해주면 된다.

홀수금액에서 5원이라는 홀수금액을 빼주면 무조건 짝수금액이 되니까 2원짜리로 무조건 처리가 가능하다.

 

한가지 유의해야할 것은, n값이 1원이 들어올수도있다는것과 3원또한 처리가 불가능하니 -1을 출력해줘야 한다.