JUMPGAME 동적계획법으로 풀었는데 ㅠㅠ 시간초과가 나네요

  • konikim
    konikim

    으으 ㅠㅠ 책에서 읽고 그대로 풀었는데
    시간초과가 뜨네요 ㅠㅠ 여기서 더 빠르게 푸는 방법이 있다고는 했는데 동적계획법으로도 풀수있다고 하셔서... 계속 트라이 해봤는데 잘 모르겠네요 ㅠㅠ 어떻게 해야 시간초과가 안날까요? 도와주세요!

    #include<stdio.h>
    #define _CRT_SECURE_NO_WARNINGS
    int n;
    int board[100][100];
    int cache[100][100];
    
    int jump(int y, int x) {
        int jumpsize;
    
        //기저사례 처리
        if (y >= n || x >= n)
            return 0;
        if (y ==( n - 1) && x == (n - 1))
            return 1;
        int ret = cache[y][x];
        if (ret != -1)
            return ret;
        jumpsize = board[y][x];
        return ret = (jump(y + jumpsize, x) || jump(y, x+jumpsize));
    }
    
    int main() {
        int c, i, j, k;
        for (i = 0; i < 100; i++)
            for (j = 0; j < 100; j++)
                cache[i][j] = -1;
        scanf("%d", &c);
        for (i = 0; i < c; i++) {
            scanf("%d", &n);
    
            for (j = 0; j < n; j++) {
                for (k = 0; k < n; k++) {
                    scanf("%d", &board[j][k]);
                    cache[j][k] = -1;
                }
            }
            if (jump(0, 0)==1)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    

    3년 전
1개의 댓글이 있습니다.
  • 우인명
    우인명

    int ret = cache[y][x]; 이부분 참조자를 빼먹으셨어요
    int &ret = cache[y][x]; ㄱㄱ~


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