동적계획법 문제) JUMPGAME- 시간초과

  • lamourse
    lamourse

    JUMPGAME 질문

    JUMPGAME

    동적계획법으로 풀어본 코드 아래에 첨부합니다.
    답안 제출해보니 시간초과라고 뜨는데 .. 이유를 알 수 있을까요?
    답안번호는 329045입니다.
    도움 부탁드립니다

    제 코드

    #include <stdio.h>

int mem[100][100];
int arr[100][100];
int n;

int jump2(int x, int y){
    if (x >= n || y >= n){ return 0; }
    if (x == n - 1 && y == n - 1){ return 1; }
    if (mem[x][y]==1){ return 1; }
    int jump = arr[x][y];
    return mem[x][y] = jump2(x + jump, y) || jump2(x, y + jump);
}

int main(void){
    int tc = 0;
    scanf("%d", &tc);
    for (int t = 0; t < tc; t++){
        scanf("%d", &n);
        if (tc < 0 || tc>50){ return -1; }
        if (n < 2 || n>100){ return -1; }
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++)
            {
                mem[i][j] = 0;
                scanf("%d", (arr[i]) + j);
            }
        }
        if (jump2(0, 0)){ printf("YES\n"); }
            else printf("NO\n");
    }
}

    9년 전
2개의 댓글이 있습니다.
  • Elevista
    Elevista

    보면 mem[x][y]에 값을 넣는걸 모든 완전 탐색이 끝난 뒤에 넣으셨네요.
    if (mem[x][y]==1){}에 printf 넣어보세요.
    한 번도 참조가 되지 않을거에요 아마.

    mem[x][y]는 해당 지점에서 재귀 탐색을 최초 1회만 실시 하기 위해 최초 방문 했을때만 값을 변경하고 그 후에 재귀 탐색을 실시하고 다음 방문시 값이 변경되어 있으면 재귀 탐색을 하지 않고 바로 리턴하는 형식으로 쓰이면 될 것 같아요.


    9년 전 link
  • defector
    defector

    제 생각엔 이 문제에서 mem 효과를 얻으려면, 실패한 것에 대한 값을 저장하는 것이 중요한 부분인 것 같은데용.
    위 코드에서는 성공했을 때(1) 에만 return 1 하고 있네요.
    실패한(0) 경우에도 바로 return 해줄 수 있도록, mem에 대한 초기화를 다른 값으로 해주면 되지 않을까 싶어요.


    9년 전 link

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