[C/C++] 백준 - 11060번 : 점프 점프

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

11060번: 점프 점프

문제

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

 

BFS처럼 갈 수 있는 경로를 택해 끝까지 이동하면서 확인된 경로는 메모이제이션을 적용하여 저장해준다. 이걸 어떻게 구현해야할까를 고민했다. 

 

위치에 대한 값만 저장을 ([방문한 위치] -> 1차원 배열 형태)하려고 한다면 정답이 아닌 경로로 전에 방문한 이력이 있다면 방문해보지도 못한채 반환되어버린다. 그렇기 때문에 [방문한 위치를, 몇 번째 점프를 통해] 도달했는지 저장해주기로 하였다.

 

-> 그래서 2차원 배열의 형태로 메모이제이션을 적용시켜주었다.

2차원 배열의 형태로 메모이제이션을 적용시켜주면 현 위치에 같은 횟수 점프로 도달한 이력만 반환받기 때문에 위에서 우려한 부분을 해결할 수 있다.

#include <iostream>
#include <vector>
#define INF 987654321
using namespace std;

int N;
int cache[1003][1003];
vector<int> jump;

int path(int pos, int cnt){
    if(pos >= N) return cnt;
    if(jump[pos] == 0) return INF;
    int &ret = cache[pos][cnt];
    if(ret != -1) return ret;
    ret = INF;
    for(int next = 1; next <= jump[pos]; next++){
        ret = min(ret, path(pos+next, cnt+1));
    }
    return ret;
}

void input(){
    cin >> N;
    jump = vector<int>(N+1,0);
    for(int i=1;i<=N;i++) cin >> jump[i];
    memset(cache, -1, sizeof(cache));
    int answer = path(1, 0);
    if(answer==INF) answer = -1;
    cout << answer << endl;
}

int main(){
    fastio; 
    input();

    return 0;
}