백준[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;
}
Share