백준 1890 C++ 풀이

DFS로 풀라고 해서 풀었더니. 시간 초과가 떴습니다 (그럼 왜 DFS로 풀라고 한 건지 ㅡㅅㅡ )

DP로 푸니까 답이 안 나와서 보니까.

맨 마지막 route에서 DFS 를 호출해서 값이 과장된 게 문제였어요.

고치고 제출하니 틀렸스빈다 뜨길래,

이번엔 경로값을 int에서 롱롱으로 바꿨더니 통과.

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int buffer[1001][1001];
long long route[1001][1001];
int number;
int N;
void DFS(int x, int y) {
    int temp = buffer[x][y];
    if (x == N-1 && y == N-1) return;
    if (x + temp < N) {

        route[x + temp][y] += route[x][y];
      //  cout << x + buffer[x][y] << y << "marked" << route[x + buffer[x][y]][y] << endl;
    }
    if (y + temp < N) {

        route[x][y + temp] += route[x][y];

        //cout << x << y + buffer[x][y] << "marked" << route[x][y + buffer[x][y]] << endl;
    }
}
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> N;
    number = 0;
    for (int y = 0; y<N; y++) {
        for (int x = 0; x < N; x++) {
            cin >> buffer[x][y];
        }
    }
    for (int y = 0; y<N; y++) {
        for (int x = 0; x < N; x++) {
            route[x][y] = 0;
        }
    }

    route[0][0] = 1;
    for (int y = 0; y<N; y++) {
        for (int x = 0; x < N; x++) {
            DFS(x, y);
        }
    }

//    for (int y = 0; y<N; y++) {
//        for (int x = 0; x < N; x++) {
//            cout << route[x][y] << ' ';
//        }
//        cout << '\n';
//    }
    cout << route[N - 1][N - 1] << endl;
    return 0;
}