백준[1890] - 점프

문제

백준 1890 문제 보기

접근 방법

그냥 완전탐색으로 문제를 풀 경우 시간 초과가 났다. 따라서 중간 중간 메모이제이션을 활용해 값을 저장했다.

코드

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int N;
int map[100][100];
long long int dp[100][100];

long long int dfs(int r, int c) {
    // 범위 밖
    if(r < 0 || c < 0 || r >= N || c >= N)
        return 0;
    // 이전 방문 여부
    if(dp[r][c] > 0) {
        return dp[r][c];
    }
    // 도착지
    if(r == N - 1 && c == N - 1) {
        dp[r][c] = 1;
        return dp[r][c];
    }
    // 길 x
    if(map[r][c] == 0) {
        return 0;
    }

    // 두 가지의 경우를 더해서 저장
    long long int num = dfs(r + map[r][c], c) + dfs(r, c + map[r][c]);

    // 메모이제이션
    dp[r][c] = num;
    return dp[r][c];
}

int main() {
    cin >> N;

    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            cin >> map[i][j];
        }
    }

    memset(dp, 0, sizeof(dp));
    cout << dfs(0, 0);
    return 0;
}