[백준 c++] 11060 점프 점프

---

문제

https://www.acmicpc.net/problem/11060
1×N 크기의 미로가 있다.
각 칸에 적힌 수만큼 오른쪽으로 이동할 수 있다.
예를 들어 3번 째 칸에 3이 적혀있으면 4, 5, 6번째 칸으로 이동할 수 있다.
맨 왼쪽 칸에서 맨 오른쪽 칸으로 이동하려고 할 때 최소 몇 번 점프를 해야하는지 구하여라.

---

풀이

각 칸은 여러 출발지가 가능하다는 점을 고려해서 문제를 풀었다.

dp[index] = index칸까지 점프한 횟수

입력으로 2 1 3 이 있을 때
1번 째 칸은 2칸까지 점프할 수 있으므로
2, 3번 째 칸의 점프 횟수는 dp[0] + 1 이다.
dp[1] = dp[0] + 1 = 1
dp[2] = dp[0] + 1 = 1

2번 째 칸은 1칸 점프할 수 있으므로
3번 째 칸의 점프 횟수는 dp[2] + 1 = 2가 될 수 있지만,
최소 횟수를 구하는 것이므로 기존에 저장된 dp[2]의 값인 1로 유지된다.

또한 i번 째에 0이 나왔는데 0이 유일한 출발지인 경우( dp[i+1] ==0 ) -1을 출력하도록 한다.

---

코드

#include <iostream>
using namespace std;
int n, a, dp[1001], ret;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a;
        if (!a && !dp[i + 1] && i < n)
        {
            ret = 1;
            break;
        }
        for (int j = i + 1; (j <= i + a) && (j <= n); j++)
        {
            if (!dp[j])
                dp[j] = dp[i] + 1;
        }
    }

    if (ret)
        cout << -1 << "\n";
    else
        cout << dp[n] << "\n";
}