외발 뛰기 (문제 ID: JUMPGAME, 난이도: 하)

★★★★★다시 풀어 볼 문제★★★★★

알고리즘 문제해결 전략 1권

외발 뛰기 (문제 ID: JUMPGAME, 난이도: 하)

나름 DP문제는 많이 풀어봤다고 생각했지만 , 이 문제처럼 TRUE FALSE로 답을 내는 문제는 처음이었다.

내가 푼 DP문제들은 경우의 수를 구하는 문제가 대부분이었다.

그러다 보니 약간 생소한 느낌이고, 다른 문제를 푸는 느낌이었다.

그래서 풀어보는데 이해가 안가고 고민해야 했던 부분이 많았다.

# 내가 지금까지 풀어온 DP는 뭔가 점화식을 정하고 풀어야 한다는 강박관념이 있었는데,

이 문제는 그냥 재귀함수로 원하는 칸에 도달할 때까지 풀면서, 메모이제이션만 하면 됐다.

물론 이 과정에서 점화식을 구하고 풀어도 되겠지만 딱히 점화식이라고 생각하지 않았다(개인적으로)

코드적 스킬은 마지막 check[x][y] 를 || 연산으로 묶어줘서 판별하는 방식을 배웠다!

코드

#include<iostream>
#include<string.h>
using namespace std;
 
int map[101][101];
int check[101][101];
int n;
int jump(int x, int y)
{
    if (x >= n || y >= n)
    {
        return 0;
    }
    if (x == n - 1 && y == n - 1)
    {
        return 1;
    }
 
    if (check[x][y] != -1)
    {
        return check[x][y];
    }
 
    check[x][y] = (jump(x + map[x][y], y) || jump(x, y + map[x][y]));
 
    return check[x][y];
    
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        memset(check, -1, sizeof(check));
        memset(map, -1, sizeof(map));
 
        cin >> n;
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> map[i][j];
            }
        }
 
        int c = jump(0, 0);
 
        if (c==1)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
 
    }
 
    return 0;
}