[알고스팟] Jump Game - 동적 계획, 메모이제이션

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 

 

점프 게임(링크)

게임판의 각 지점에 적힌 숫자대로 오른쪽 또는 아래로 이동할 수 있으므로 대략 2^(격자 개수) 가지의 경우의 수가 있다.최대 100 x 100개의 칸이 있으므로 모든 칸에서의 도달 가능 여부를 검사하기는 무리다. 

 

그런데 어떤 지점들은 여러 경로로 도달할 수 있다. 즉, 중복으로 계산되는 경로가 있으므로 한번 계산한 경로는 저장하고 필요할 때 꺼내서 사용한다.

 

#include <iostream>
#include <vector>
using namespace std;

// Initial state: -1, NO: 0, YES: 1
int cache[100][100];

int jumpGame(vector<vector<int>> board, int y, int x) {
    int goal = board.size() - 1;
    // Out of range.
    if (goal < y || goal < x) return 0;
    // Arrived!
    if (goal == y && goal == x) return 1;

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

    return ret = jumpGame(board, y + board[y][x], x) || jumpGame(board, y, x + board[y][x]);
}