BOJ 1890번 점프

BOJ : https://www.acmicpc.net/problem/1890

github : https://github.com/junho0956/Algorithm/blob/master/1890/1890/%EC%86%8C%EC%8A%A4.cpp

 

종착점인 arr[N-1][N-1] 부분만 0이 나오는줄 알았는데

다른 부분에서도 0이 나올수있는지 메모리초과 덕분에 알았습니다.

문제를 좀더 꼼꼼하게 읽는 습관을 들여야겠습니다.

 

문제가 요구하는 그대로 재귀식 dp를 활용하여 해결하였습니다.

 

#include <iostream>
using namespace std;
 
typedef long long ll;
 
ll dp[101][101];
int arr[101][101];
int N;
 
ll solve(int y, int x) {
    if (y == N - 1 && x == N - 1) return 1;
    if (y >= N || x >= N) return 0;
    if (arr[y][x] == 0) return 0;
 
    ll& res = dp[y][x];
    if (res) return res;
 
    return res = solve(y + arr[y][x], x) + solve(y, x + arr[y][x]);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> arr[i][j];
 
    cout << solve(0, 0);
    return 0;
}