[백준] 14916 거스름돈

가장 기본적인 그리디 문제이다!

처음에 일단 거스롬돈을 최대한 5원으로 줘야지 거스롬돈 동전 수가 적어지므로 5원을 가능한 만큼 쓴다. 하지만 이후에 2원으로만 거스름돈을 줘야하기에 5원으로 채워진 돈 외에 남은 거스름돈은 짝수가 되어야한다!

만약 짝수가 아니라면 채웠던 5원을 하나 빼준다.

그 후 남은 거스롬돈을 2원으로 가능한 만큼 채운다!!

이때 남은 거스름돈이 0원으로 딱 떨어지면 동전을 count한 값을 출력하고, 아닌 경우 -1을 출력한다.

 

#include <cstdio>
using namespace std;
int n, cnt = 0;
int main()
{
    scanf("%d", &n);
    while (n - 5 >= 0)
        cnt++, n -= 5;
    if (cnt && n % 2 == 1)
        cnt--, n += 5;
    while (n - 2 >= 0)
        cnt++, n -= 2;
    if (n != 0)
        printf("-1");
    else
        printf("%d", cnt);

    return 0;
}

 

Uploaded by Notion2Tistory v1.1.0