동전 2 - 2294

//2293 - 동전 2
//슬라이딩 윈도우 최적화
 
#include <iostream>
using namespace std;
 
#define INF 100000
 
int N, K;
int arr[100];
int cache[10001];
 
void init()
{
    cin >> N >> K;
    for (int i = 0; i < N; ++i)
        cin >> arr[i];
    for (int i = 0; i <= K; ++i)
        cache[i] = INF;
    cache[0] = 0;
}
 
int dp(int cost)
{
    if (cost < 0)
        return INF;
    return cache[cost];
}
 
int main()
{
    init();
    for (int i = 0; i < N; ++i)
        for (int cost = 1; cost <= K; ++cost)
            cache[cost] = min(cache[cost], dp(cost - arr[i]) + 1);
    if(cache[K] == INF)
        cout << -1;
    else
        cout << cache[K];
}

 

 

 

 

 

 

 

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

2294번: 동전 2

 

 

 

 

 

 

동전 2

dp문제

C(idx, cost) : 0-idx까지의 동전을 사용했을때, 가장 적은 동전을 사용해 cost를 만들었을 때 동전의 개수

C(idx, cost) = min( C(idx-1, cost) , C(idx, cost - d[idx] )

https://onedaycoding.tistory.com/77

동전 1 - 2293

위 링크의 최적화를 똑같이 적용했습니다.