ESCAPEGEESE 문제 알고리즘 문의드립니다.

  • rapguy
    rapguy

    안녕하세요~ 항상 도움 주셔서 감사합니다.^^

    제가 ESCAPEGEESE 를 풀고 있는데 시간초과를 해결하지 못해서 힌트 문의드립니다.

    기존에 http://algospot.com/forum/read/2041/ 에서 힌트가 있던데요.
    아직 이해를 못해서 TT 동적계획 알고리즘 적용을 못하고 있습니다.

    아래와 같은 방법으로 하면 N=500, K=100 일때 시간이 오래 걸리네요.
    (아래 알고리즘은 0번오리가 탈출을 했을때와 0번 오리가 탈출을 하지 못했을때로 나누어서
    재귀로 cache 를 쓴건데 답은 나오지만 빠르지 않네요..)

    위에 http://algospot.com/forum/read/2041/ 보다 조금 더 자세한 설명이 가능할런지요?
    감사합니다.~

    #include <stdio.h>
#include <string.h>

const int MOD = 1000000007;
int T, N, K;
int cache[500][500][100];

int func(int mod, int idx, int escape)
{
    if(escape == K) return mod == 0;
    if(idx >= N) return 0;

    int& ret = cache[mod][idx][escape];
    if(ret != -1) return ret;
    ret = (func(mod, idx + 1, escape) + func((mod + idx) % N, idx + 1, escape + 1)) % MOD;
    return ret;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d %d", &N, &K);
        memset(cache, -1, sizeof(cache));
        printf("%d\n", func(0, 0, 0));
    }
    return 0;
}


    10년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.