[BOJ-11060]점프 점프

[문제요약]

1*N으로 구성된 미로가 있다. 왼쪽 끝부터 오른쪽 끝으로 이동하는데 이 때, 최소 몇 번 점프를 해야 갈 수 있는지를 구한다.

각 미로의 칸에는 임의의 숫자 [0,100] 이 적혀있고 각 위치가 i번째라 하면 Ai ~[0, 100] 은 이동할 수 있는 칸의 수를 의미한다.

각 칸의 Ai 는 적힌 수 이하의 수만큼 오른쪽으로 이동할 수 있다.

만약 도달하지 못하는 경우 -1을 출력한다.

[입력]

N~[1, 1000] : 미로의 크기가 주어진다

A0 ~ AN-1 : 각 칸의 점프 가능 횟수가 주어진다.

[출력]

왼쪽 끝부터 오른쪽 끝까지 이동하는 최소 점프 횟수를 출력한다.

최소 점프 횟수가 없는 경우 -1 을 출력한다.

[접근방법]

각 칸을 최소 이동횟수로 갱신시키는 문제였다.

처음 시작위치는 이동횟수가 0 으로 초기화 되어있고, 마지막 도달하는 위치의 횟수는 1000을 넘어갈 수 없다. 

그렇기 때문에 모든 칸을 먼저 1000 이상의 수인 INF으로 설정한다. 

그리고 각 칸의 값을 갱신시키면 된다.

[C++11 source code DP]

#include<cstdio>
#define din1(a) scanf("%d", &a)
const int M = 1111;
const int INF = 1111;
int ans[M];
int imap[M];
 
 
 
void init() {
    for (int i = 0; i < M; i++) ans[i] = INF;
}
 
int main() {
    init();
    int N;
    din1(N);
    for (int i = 0; i < N; i++) {
        din1(imap[i]);
    }
    ans[0] = 0; // init
    for (int here = 0; here < N; here++) {
        for (int there = here+1 ; there <= here +imap[here]; there++) {
            ans[there] = (ans[here] + 1 <= ans[there]) ? ans[here] + 1 : ans[there];
        }
    }
 
    if(ans[N-1] != INF)    printf("%d", ans[N-1]);
    else puts("-1");
 
    return 0;
}