2294번

2294번 - 동전 2

DP 문제를 풀면서, 이게 정말 왜 안풀리지라는 고민을 엄청 많이했다.

보통의 DP와 비슷하게 접근하고, 정말 맞았다고 생각하는데도 계속 시간초과가 발생했다.

처음에는 다시 풀어야겠다 라고 넘어갔었지만, 1520번 문제를 풀면서 갑자기 머리가 땡 하면서 문제가 해결 됐다.

1520문제와 같이 memoization 의 초기값 설정 문제였다.

DP 라는 것은 결국 같은 문제를 풀 때, 이미 저장된 값을 이용해서 문제를 빠르게 풀도록 도와주는 memoization 을 사용한다.

그럼에도 계속 시간 초과가 났던 이유는

1520 문제와 비슷하게, 이 문제는 정답이 무조건 있는게 아니라, 어떠한 경우는 정답이 발생하지 않는다는 점이었다.

처음에 짰던 틀린 코드를 보자.

캐시값의 초기값은 987654321 로 저장되어있다. 그래서 N번째 수를 만들 수 없어도 987654321 로 저장이 된다.

그래서 N번째 수를 만들 수 없다는 사실을 아는데도, 계속 방문해서 계산을 하게 된다. 여기서 시간이 늘어났다.

정답 코드를 다시 보면,

캐시의 초기값은 -1 로 설정되어있고, 방문했지만, N값을 만들 수 없으면 987654321 로 저장이 된다.

즉 정답코드에서는 방문 안함 과 방문했지만 답이 없다 를 나눠주는 코드가 중간에 존재한다는 점이다.

방문 안함과 방문했지만 답이 없다는 빼먹을 수도 있지만, 속도에서 중요한 차이가 발생한다.

즉, 답이 없다라는 것도 어떻게 보면 답이 있다는 것이다... 즉 캐시에 저장될 값이라는 점!!

이 문제에서 큰 깨달음을 얻은 듯 했다!

<정답 코드>

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
int n, k;
vector<int> coin;
int D[10001];
 
int go(int K)
{
    if (K == 0)
    {
        return 0;
    }
    if (D[K] != -1)
    {
        return D[K];
    }
 
    if (D[K] == -1)
    {
        D[K] = 987654321;
    }
    for (int i = 0; i < coin.size(); i++)
    {
        if (K - coin[i] >= 0)
        {
            D[K] = min(D[K], go(K - coin[i]) + 1);
        }
    }
 
    return  D[K];
}
int main()
{
    scanf("%d %d", &n, &k);
    coin.resize(n);
    for (int i = 0; i < 10001; i++)
    {
        D[i] = -1;
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &coin[i]);
    }
    sort(coin.begin(), coin.end());
    reverse(coin.begin(), coin.end());
 
    int ans = go(k);
 
    if (ans == 987654321)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", ans);
    }
 
 
 
    return 0;
}

<처음 짰던 틀린 코드>

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
int n, k;
vector<int> coin;
int D[10001];
 
int go(int K)
{
    if (K == 0)
    {
        return 0;
    }
    if (D[K] != 987654321)
    {
        return D[K];
    }
    for (int i = 0; i < coin.size(); i++)
    {
        if (K - coin[i] >= 0)
        {
            D[K] = min(D[K], go(K - coin[i]) + 1);
        }
    }
 
    return  D[K];
}
int main()
{
    scanf("%d %d", &n, &k);
    coin.resize(n);
    for (int i = 0; i < 10001; i++)
    {
        D[i] = 987654321;
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &coin[i]);
    }
    sort(coin.begin(), coin.end());
    reverse(coin.begin(), coin.end());
    
    int ans = go(k);
 
    if (ans == 987654321)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", ans);
    }
    
 
 
    return 0;
}