글 읽기 - 재귀함수로 풀어보았는데 시간초과가 나옵니다. 도와주세요.

mhccc 5년 전 0

계속해서 시간초과가 나오네요 ㅜㅜ

혹시 어떤 부분이 잘못됐는지 알 수 있을까요??

도움 부탁드립니다!!

#include <iostream>
using namespace std;
int a[100][100];
int n;
long long ans;
void go(int x, int y) {
    if(x >= n || y >= n) return;
    if(x == n-1 && y == n-1) {
    	ans++;
    	return;
    }
    if(a[x][y] == 0) return;
    go(x+a[x][y], y);
    go(x, y+a[x][y]);
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> a[i][j];
        }
    }
    go(0, 0);
    cout << ans;
    return 0;
}

jh05013 5년 전 0

재귀함수로 풀었기 때문에 시간 초과입니다. 이런 종류의 재귀함수를 빠르게 하는 알고리즘이 무엇이었는지 기억을 떠올려 보세요.

djm03178 5년 전 0

이렇게 풀면 안 된다는 뜻입니다. 답이 2^63-1보다 작거나 같다고 되어있는 건 거기까지 답이 올라가게 만들 수 있기 때문에 쓰여있는 것이고, 2^63-1가지의 경우의 수를 하나씩 세는 건 수명이 다하기 전까지 끝을 볼 수 없는 수준입니다.

다이나믹 프로그래밍을 사용해야 합니다.

mhccc 5년 전 0

답변 감사합니다!

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

문제

문제

출처

ICPC

재귀함수로 풀어보았는데 시간초과가 나옵니다. 도와주세요.

mhccc 5년 전 0

jh05013 5년 전 0

djm03178 5년 전 0

mhccc 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말