[알고스팟 JUMPGAME] 외발뛰기 C++

algospot.com/judge/problem/read/JUMPGAME

algospot.com :: JUMPGAME

동적계획법이 정말 도저히 이해가 안가서 종만북 이라는 알고리즘 책을 보기 시작했다.

종만북에 나온 문제가 웹에도 있으니 종만북 공부하면서 푼 코드들을 업로드할 예정

종만북보고 내가 따로 코드를 작성하는거라 종만북 답지랑은 아마 다를것임

 

 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
int c, n;
int arr[100][100];
int dp[100][100];
 
int jump(int x, int y) {
    //기저사례 : 마지막칸에 도착한경우
    if (x == n - 1 && y == n - 1) return 1;
    //기저사례 : 게임판 밖을 나간경우
    if (x >= n || y >= n) return 0;
 
    //메모이제이션
    if (dp[x][y] != -1) return dp[x][y];
 
    dp[x][y] = (jump(x + arr[x][y], y) || jump(x, y + arr[x][y]));
 
    return dp[x][y];
}
 
int main() {
 
    cin >> c;
 
    while (c--) {
        cin >> n;
        memset(dp, -1, sizeof(dp));
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                cin >> arr[i][j];
            }
        int result = jump(0, 0);
        if (result == 1)
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
    }
    return 0;
}

 

재귀에대해 조금은.. 알아가는느낌