2294번 동전2

문제 링크

동전2

문제 풀이

동전이 서로 배수가 아니기 때문에 그리디로 풀 수 없다. 따라서 현재 동전을 하나 사용할때와 안할때 모두 찾아봐야 한다. 남은 가치가 remain으로 두면, 기저 사례를 remain이 0 일때로 두고, 또한 remain이 0 이 아닌데 사용할 수 있는 동전이 없는 경우도 기저 사례로 둔다. 그 후 현재 동전을 사용하지 않고 넘어가는 경우와 사용할 수 있을 경우 하나 사용하는 경우를 재귀 호출한다.
지금 cache를 2차원 배열로 하여 문제를 풀었는데, 이를 1차원으로 싶으면 반복문으로 풀어야 한다.

구현

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

const int INF = 987654321;
int N, K;
int coin[101], cache[10001][101];

int solve(int remain, int coinNum) {
    if (remain == 0) return 0;
    if (coinNum == N) return INF;

    int& ret = cache[remain][coinNum];
    if (ret != -1) return ret;

    ret = solve(remain, coinNum + 1);
    if(remain >= coin[coinNum]) 
        ret = min(ret, solve(remain - coin[coinNum], coinNum) + 1);
    
    return ret;
}

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

    cin >> N >> K;
    for (int i = 0; i < N; ++i)
        cin >> coin[i];
    memset(cache, -1, sizeof(cache));
    
    int ret = solve(K, 0);
    cout << ((ret == INF) ? -1 : ret);
    return 0;
}