[동적계획법] 1.외발뛰기

종만북 8장 동적계획법. 8.1. JUMPGAME

 

https://algospot.com/judge/problem/read/JUMPGAME

 

동적 계획법으로 풀었다.

그래프 문제로도 접근할 수 있다고 한다.

 

---

8.1. 외발뛰기(JUMPGAME) 코드 (정답, 20ms)

/**
 * @name    8.1.외발뛰기
 * @ID      JUMPGAME
 * @date    2019-08-04
 * @author  Sunmon
 */
#include <iostream>
#include <cstring>

int n, board[100][100], cache[100][100];
using namespace std;


//(y,x)부터 (n-1, n-1)까지 도달할 수 있으면 1, 아니면 -0 리턴
int jump(int y, int x)
{
    if(y >= n || x >= n) return 0;
    if(y == n-1 && x == n-1) return 1;

    int& ret = cache[y][x];
    if(ret!=-1) return ret;

    int jumpSize = board[y][x];
    return ret = (jump(y+jumpSize, x) || jump(y, x+jumpSize));
}

int main()
{
    int c;  //test case
    cin >> c;
    while(c--)
    {
        cin >> n;
        for(int j = 0; j<n; j++)
        {
            for(int i = 0; i<n; i++)
            {
                cin >> board[j][i];
            }
        }
        memset(cache, -1, sizeof(cache));
        int ans = jump(0,0);
        ans == 1? cout << "YES\n" : cout << "NO\n";
    }
}