[백준 14916번] 거스름돈

14916번: 거스름돈 (acmicpc.net)

14916번: 거스름돈

2원과 5원으로 거스름돈을 최소의 개수의 동전으로 거슬러줘야하는 문제

사실 이거 틀렸어서 엄청 고민했었는 데 알고보니 n==1 || n==3인 예외의 경우를 안해줘서였음

문제를 끝까지 똑바로 읽자! ^.^

 

먼저 5의 배수이면 5원으로 모두 거슬러주는 게 최소다

그래서 먼저 else if로 5의 배수인지 체크해서 걸러줬다.

 

그 다음, 5의 배수가 아니고 예외인 1과 3을 걸러주면 남은 숫자가 2, 4, 6, 7, 8, 9, 11, 12, 13, ... 임

6원 같은 경우는 5원으로 거슬러주고 남은 게 1원이기 때문에 안됨

 

따라서 숫자를 5로 나눴을 때의 나머지가 2이면, 5원들로 거슬러주고 나머지를 2원들로 거슬러주면 됨!

그렇지 않은 경우는, 5로 나눈 거의 1만큼 뺀만큼 5원으로 거슬러주고, 나머지를 2원으로 거슬러주면 됨. (ex. 8원 -> 2원*4개, 11원->5원*1 + 2원*3)

 

그걸 코드로 표현해주면

#include <iostream>
using namespace std;

int main()
{
    int n;
    int cnt=0;
    cin>>n;
    
    if(n==1 || n==3) cnt=-1;
    
    else if(n%5==0){
        cnt += n/5;
    }
 
    else if((n-n/5)%2==0){
        cnt += n/5;
        n -= cnt*5;
        cnt += n/2;
    }
       
    else {
        cnt += n/5-1;
        n -= cnt*5;
        cnt += n/2;
    }

    cout <<cnt<<endl;
    return 0;
}