# 백준 : 거스름돈(5585)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_5585_change)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;

#define MAX 1000

int dp[MAX + 1];
int species[7] = {1, 5, 10, 50, 100, 500};

int main(void)
{
    int price, change;
    cin>>price;
    change = 1000 - price;
    
    dp[0] = 0;
    for(int i=1; i<=change; i++) {
        dp[i] = MAX;
        for(int j=0; j<6; j++) {
            if(species[j] <= i) {
                dp[i] = min(dp[i], dp[i - species[j]]) + 1;
            }
        }
    }
    cout<<dp[change]<<endl;
    return 0;
}

풀이

아마도(Maybe) DP를 이용해서 풀라고 만들어 놓은 문제같지는 또 않은것 같은데..
우선 나는 DP를 이용했다. 굉장히 쉽게 접근했는데, 의외로 답이 잘 구해지지 않았다.
문제는 int species[7]을 {500, 100, 50, 10, 5, 1} 순으로 해놓고 계산을 하면 오답이 나오는 것을 확인했다. 아마도 비교하는 시점이 점점 늘어나면서 min을 잘못 구하는 것 같은데..
사실 원리대로 이해하면 뭐가되었든 최소값이 나와야 하니까 답은 제대로 나올 것 같았는데..
무튼 잘 모르겠다. 순서를 바꿔버리면 답이 나오는 것을 확인했다.