[BOJ 1414] 사탕

GㅎDP공부를 시작해서 만난문제중 처음으로 푸는데 1~2일정도 시간이 소요된 문제이다.

void eratos(int n)
{
    if(n<=1) return;

    for (int i = 2; i <= n; ++i)
        prime_array[i] = true;
    for (int i = 2; i*i <= n; ++i) {
        if(prime_array[i])
            for (int j = i*i; j <= n; j+=i) {
                prime_array[j] = false;
            }
    }
}

소수를 다루는 문제이기 때문에 에라토스테네스의 체를 사용해야한다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

캔디의 경우 같은 가격이 같은 종류이기 때문에 문제를 조금 다르게 보았다.

1,1,1,2,3 같은경우 1+1+3=5 와 2+3=5 둘은 다른 경우지만 또 다른 1+1+3 = 5가 나올수가 있기때문에 이러한 중복연산을 제거 해줘야한다.

    for (int i = 0; i < N; ++i) {
        int amount = 1;
        if(candy_price[i]==-1)
            continue;
        candy.push_back(vector<int>());
        candy[candy.size()-1].push_back(candy_price[i]);
        for (int j = i+1; j < N; ++j) {
            if(candy_price[i] == candy_price[j])
            {
                candy[candy.size()-1].push_back(candy_price[i]*(++amount));
                candy_price[j]=-1;
            }
        }
    }

한 종류의 캔디가 몇개가 있는지로 문제를 변형해 이렇게 풀었는데 사실 저렇게 벡터로 복잡하게 할 필요없이 배열을 가격의 최대크기만큼 파서 그 가격이 있는부분만 ++ 해주면 될 것 같다.

 

이후 이제 DP를 적용시켜서 풀면 된다.

종만북을 기반으로 공부를 했기 때문에 제일처음 구현했던 방법은 메모이제이션 기법이였다.

long long D(int idx, int count, int value)
{
    long long &ret = cache[idx][value];
    if(ret != -1)
    {
        return ret;
    }
    if(idx==candy.size())
    {
        if(prime_array[value])
        {
            return ret=1;
        }
        else
            return ret=0;
    }
    ret=D(idx+1,0,value);
    for (int i = 0; i < candy[idx].size(); ++i) {
        int added_value = value + candy[idx][i];
        ret+=D(idx+1,i+1,added_value);
    }
    return ret;
}

잘 작동해서 바로 제출 했더니 메모리 초과란다. 아무래도 500000*50*sizeof(long long)이 문제의 조건에 부합하지 않았던 것같다.

 

검색을 해보니 슬라이딩 윈도우라는 기법이 있었다. 이는 DP를 적용할때 바로 앞 행만 참고해도 되는 경우

그 전의 행 데이터는 보관할 필요가없기 때문에 결국 앞행 + 현재행 해서 2개의 행으로 메모리를 줄여 문제를 풀어나갈 수 있는 방법이다.

저 메모이제이션 기법으로는 이제 더이상 해결할 수 없기때문에

https://www.acmicpc.net/problem/2293 동전 1 문제를 풀었던 기억을 되살려

    for (int i = 0; i < candy.size(); ++i)
    {
        for (int j = 0; j < candy[i].size(); ++j) {
            int in = candy[i][j];
            if(i==0)
                cache2[in]++;
            else
            {
                // cache2[in]++;
                for (int k = 0; k <= sum_value; ++k) {
                    if(k-in>=0)
                        cache2[k] = cache2[k] + cache1[k-in];
                }
            }
        }
        memcpy(cache1,cache2,sizeof(cache1));
    }
    long long p_count = 0;
    for (int i = 0; i <= sum_value; ++i)
        if(prime_array[i])
            p_count+=cache1[i];
    printf("%lld\n", p_count);

문제를 해결하였다.