# 백준 : 동전 2(2294)

문제

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

소스

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

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

#define KIND 100       
#define VALUE 10000 

int values[KIND + 1] = {0,};      
int dp[VALUE + 1] = {0,};   // DP

int main(void)
{
    int penny_kind;
    int total_value;
    
    cin>>penny_kind>>total_value;
    for(int penny = 0; penny < penny_kind; penny++) {
        cin>>values[penny];
    }
    
    dp[0] = 0;
    for(int i=1; i<=total_value; i++) {
        dp[i] = VALUE;
        for(int j=0; j<penny_kind; j++) {
            if(values[j] <= i) {
                dp[i] = min(dp[i], dp[i - values[j]] + 1);
            }
        }
    }
    if(dp[total_value] < VALUE) cout<<dp[total_value]<<endl;
    else                        cout<<"-1"<<endl;
    return 0;
}

풀이

2틀정도를 계속 고민하고 도전하고.. 그러다가 계속 실패하고.
사실 DP에 대한 자신감이 엄청나게 하락하고 있을 때, 단 한번만에 이 문제를 해결했다.
기존에 존재하던 코드를 쓰지도 않았고, 처음부터 다시 작성해서 문제를 해결했다.
조금만 간단하게 생각하면 정말 간단하게 점화식을 만들고 문제를 해결할 수 있었는데, 내가 너무 어렵게만 생각한건 아니었나 싶다. (어제 문득 생각난것은, 내가 '코딩'할줄을 모르는게 아니라, '생각'할줄을 모르고 있었다라는..)

점화식은 다음과 같이 작성하였다.
주어진 동전 n개를 이용하여 만들어야 하는 최대 가치를 v라고 할 때,
1. 그 중 한개의 동전이 최대 가치 v보다 작거나 같은 경우, 
2. 이 동전을 이용하여 가치 v를 만들 수 있다는 말이 되므로
3. 그 동전을 사용하기 전 최소 동전 갯수에 + 1한 것이 당시의 가치 v를 만들 수 있는 최소 동전의 갯수
4. 물론 동전이 한개가 아닌 여러개가 v보다 작을 수 있으므로, 각 경우마다 비교해서 최소값을 저장
그러면 결국 답을 내고자 하는 최대 가치 v에서의 최소 값을 구할 수 있다.

단, 문제를 자세히 읽어보면 최대 가치는 10000이 넘으면 안된다고 하였으므로,
최종 가치 v 값이 10000이 넘으면 -1을 출력해주면 된다.