백준 2294 동전2(dynamic programming)

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

2294번: 동전 2

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX = 100 + 1;
int coin[MAX];
int cache[10001];
int n, k;
void numofCoin()
{

    cache[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = coin[i]; j <= k; j++)
        {
            cache[j] = min(cache[j], cache[j - coin[i]] + 1);
        }
    }
    if (cache[k] == 10000001)
        cout << -1;
    else
        cout << cache[k];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> coin[i];

    for (int i = 0; i <= k; i++)
        cache[i] = 10000001;

    numofCoin();
}

 

coin=[1, 3, 12] 라 가정하자. 그렇다면 기본적인 점화식은

 

dp[i] = min(dp[i-1], dp[i-3], dp[i-12]) + 1 이 된다. 이 점화식을 세우는 것 까지는 해냈는데 구현하다 막혀서 결국 구글에 검색해봤다. cache 배열에 미리 큰 값을 넣어놓고 저런 식의 이중 loop로 간단하게 구현하더라. 저런 모양의 이중 loop를 기억해둘 필요가 있을 것 같다.

 

이 문제를 풀면서 가장 크게 느꼈던 것은 다름 아닌 memset 함수였다. 제대로 알지도 못하고 이 함수를 쓰다보니 다 구현해 놓고도 계속 오류가 났다. memset 함수를 찾아서 공부해보니 내가 정말 막 쓰고 있었구나라는 생각에 조금은 한심했다..... 지금 memset 함수에 대해 정리를 하고 자야하지만 너무 졸리다. 내일 아침에 일어나서 정리해봐야 겠다.