글 읽기 - 시간초과가 납니다 도와주세요

kyskkm2537 5년 전 0

시간초과가 안날것 같은데 나네요

#include<stdio.h>
#include<algorithm>
int n, ar[101][101], cnt;

bool safe(int x, int y)
{
    return(x>=1&&x<=n)&&(y>=1&&y<=n);
}

void solve(int x, int y)
{
    if(x==n&&y==n){// 도착점에 도착하면 경우의 수 +1
        cnt++;
        return;
    }
    if(ar[x][y]==0){// 점프 x
        return;
    }
    if(safe(x+ar[x][y], y)){// 오른쪽으로 점프(가능하면)
        solve(x+ar[x][y], y);
    }
    if(safe(x, y+ar[x][y])){// 아래로 점프(가능하면)
        solve(x, y+ar[x][y]);
    }
}

int main()
{
    scanf("%d", &n);

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%d", &ar[i][j]);
        }
    }
    solve(1, 1);

    printf("%d", cnt);

    return 0;
}

yoonsang9114 5년 전 1

이 코드가 최악의 케이스로 동작하면 2^100번정도 돌거같아요. 메모이제이션에 대해 공부해보시면 쉽게 풀 수 있으실거에요

yoonsang9114 5년 전 1

2^100번도 아니고 더돌거같아요 암튼 메모이제이션!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과가 납니다 도와주세요

kyskkm2537 5년 전 0

yoonsang9114 5년 전 1

yoonsang9114 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말