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

1.문제 링크

14916

2. 풀이 전 계획과 생각

• 그리디 알고리즘으로 풀기

3. 풀이

#include<iostream>
using namespace std;

int main(){
    int n; cin>>n;
    
    int cnt=0;
    
    // 5의 배수인 경우
    if(n%5==0){
        cout<<n/5;
        return 0;
    }

    int five = n/5;
    if(five==0){
        if(n%2!=0) cout<<-1;
        else{
            cout<<n/2;
        }
    }
    else{
        while((n-(5*five))%2!=0){
            five--;
            if(five==0) break;
        }
        n=n-(five*5);
        if(n%2!=0) cout<<-1;
        else{
            int two = n/2;
            cnt = two+five;
            cout<<cnt;
        }
    }
}

1. 5의 배수인지 체크해 그렇다면 n/5가 정답.

2. 5의 배수가 아니라면 n을 5로나눈 값을 five에 저장.

3. five가 0인경우 즉, n이 5보다 작은경우, 2의 배수가 아니라면 -1을 출력. 2의 배수라면 n/2가 정답.

4. five가 0이 아닌경우, 즉 n이 5보다 큰 경우 나머지 금액이 2의 배수가 될 때까지 five를 1씩 줄이기.

5. five를 최종적으로 확정하고 n에서 나머지 금액을 저장. 근데 n이 2의 배수가 아니라면 -1 출력.

6. 나머지 n이 2의 배수라면 five + n/2가 정답.

4. 풀이하면서 고민했던 점

• 처음에 5의 배수인지를 체크하지 않아 오류가 발생했음.

5. 문제를 풀고 알게된 개념 및 소감

• 그리디 알고리즘에 대한 이해도가 올라감.