동전 1 - 2293

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

 

 

 

 

 

 

 

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

2293번: 동전 1

 

 

 

 

 

 

동전 1

DP문제 입니다.

C(idx, cost) : 0-idx 동전까지만 사용했을 때, cost를 만들수 있는 경우의 수

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

 

위의 점화식을 사용하기위해 cache를 2차원으로 모두 만들어주면 메모리제한 4MB에 걸리게됩니다.

메모리 최적화를 해줘야 하는데, 점화식을 자세히 살펴보면, idx라인을 업데이트하기 위해선 idx-1과 idx 두개의 라인만 필요로 하게 됩니다.

따라서 슬라이딩윈도 기법을 이용해 문제를 해결할 수 있습니다.

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

 

 

위의 코드를 다시 한번 최적화 할수 있습니다.

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

점화식은 사용할수 있는 동전의 개수를 하나씩 늘려주어 최종적으로 모든 동전을 사용했을 때의 경우의 수를 구하는 것입니다.

따라서 배열을 두줄 사용하지 않고, 한줄만 사용해 위에 덮어씌어 주어도 아무 문제가 없음을 알수 있습니다.