JUMPGAME 문제 메모이제이션 사용했음에도...

  • 박다은
    박다은

    안녕하세요.
    맨 처음 그저 재귀로만 백트래킹 하다가..
    시간초과가 나서 메모이제이션을 사용하고, memset함수로
    캐시배열을 초기화 하였는데도 시간초과가 났습니다.
    그래서 인풋을 받을 때 캐시도 같이 초기화를 해주었는데도
    시간초과가 뜨네요..
    문제점이 무엇인지 알 수 있을까요?
    아래는 제 소스입니다.

    #include<stdio.h>
    
    int map[105][105], memo[105][105];
    int n;
    int jump(int i, int j)
    {
        if(i >= n || j >= n)
            return false;
        if(i == n-1 && j == n-1)
            return true;
    
        int t = memo[i][j];
        if(t > 0)
            return t;
    
        int size = map[i][j];
        return t = jump(i+size, j) || jump(i, j+size);
    }
    
    int main()
    {
        int testcase;
        scanf("%d", &testcase);
        while(testcase--)
        {
            scanf("%d", &n);
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    scanf("%d", &map[i][j]);
                    memo[i][j] = 0;
                }
            }
            printf("%s\n", jump(0, 0) ? "YES" : "NO");
        }
    }
    

    4년 전
5개의 댓글이 있습니다.
  • nosiar
    nosiar

    캐시에 대입하는 부분이 없어요


    4년 전 link
  • kriii
    kriii

    memo배열을 갱신하고 있지 않습니다.
    memo배열을 갱신하더라도 문제가 있는데, 0을 리턴하는 것과 아직 방문하지 않은 것의 차이를 두지 않으셨기 때문입니다.


    4년 전 link
  • 박다은
    박다은

    따로 변수를 생성하지 않고
    메모 배열에 바로 대입하고, 메인문에서 초기화를 0이 아니라 -1로 하니까 됐네요.
    답변 해주셔서 감사합니다^^


    4년 전 link
  • cjkis
    cjkis

    헐 사진이 바꼈네여


    4년 전 link
  • Signin
    Signin

    변수를 사용하는 방식으로 작성하시려면

    int t = memo[i][j]; 대신에 레퍼런스 변수로 선언해서
    int &t = memo[i][j]; 로 하시면 됩니다.


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