1890번 : 점프

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

1890번: 점프

 

 

이 문제는 기분좋게 풀었다.

 

DP를 이용한 하향식 접근으로 문제를 해결했다. 

 

 

---

 

 

해설코드(C++).

 

 

 

 

#include <iostream>
#include <cstring>
 
using namespace std;
 
long long dp[100][100];
int arr[100][100];
int N;
 
long long solve(int r, int c) {
    if (dp[r][c] != -1)
        return dp[r][c];
 
    if (r == 0 && c == 0)
        return 1;
 
    dp[r][c] = 0;
    for (int i = r - 1; i >= 0; i--) {
        if (arr[i][c] + i == r)
            dp[r][c] += solve(i, c);
    }
 
    for (int i = c - 1; i >= 0; i--) {
        if (arr[r][i] + i == c)
            dp[r][c] += solve(r, i);
    }
 
    return dp[r][c];
}
 
int main(void) {
    freopen("input.txt", "r", stdin);
    memset(dp, -1, sizeof(dp));
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
    
    cout << solve(N - 1, N - 1) << endl;
    return 0;
}