백준 14916번. 거스름돈(c++) / Greedy

가장 최소의 수를 구하는 그리디 문제였다.

dp를 사용해서 푸는 방법도 있지만, 직관적으로 판단한다면 더 쉽게 풀 수 있다.

 

5로 나누어떨어지지 않는다면, 2를 계속 빼는 식으로 계산했다.

최종적으로, 5로 나누어 떨어지지 않아서 while문을 빠져 나왔다면

1) 2로 나누어떨어지는 경우이거나, 2) 아예 2와 5로 떨어지지 않는 수이다. ex) 3, 1...

 

// 거스름돈
#include <vector>
#include <iostream>
using namespace std;
 
int n;
vector<int> v;
int dp[100001] = {0, };
 
int main()
{
    cin>>n;
    int cnt = 0;
    while(n>0){
        if(n%5==0){
            cout<<(n/5+cnt)<<"\n";
            return 0;
        }
        n -= 2;
        cnt++;
    }
 
    if(n==0){
        cout<<cnt<<"\n";
    }else{
        cout<<"-1"<<"\n";
    }
 
    return 0;
}