#include <iostream>
using namespace std;
int a[2001];

int d[2001];
int main(void)
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    if (n == 1)
    {
        cout << 0;
        return 0;
        ;
    }
    for (int i = 0; i < n; i++)
    {
        d[i] = -1;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j <= a[i]; j++)
        {
            if (i + j >= n)
                continue;
            if (d[i] == -1 && i != 0)
                continue;
            if (d[i + j] == -1 || d[i + j] > d[i] + 1)
                d[i + j] = d[i] + 1;
        }
    }

    if (d[n - 1] == -1)
        cout << -1;
    else
        cout << d[n - 1] + 1;
}

문제 접근

가장 왼쪽끝에 위치하고 가장 오른 쪽으로 가려고 할 때, 최소 점프 횟수 -> DP

해결 방법

다이내믹 프로그래밍을 이용한다.
d[i] = 위치 i 까지 이동했을때 걸리는 최소 점프 횟수
따라서 1~ a[i]을 더한 만큼 i 가 이동할 수 있고 이를 j 로 놓았다.
d[ i + j] = max (d[i+j], d[i] +1) 로 생각할 수 있다.

의문점 및 헷갈린 점

5
00010 같은 테스트 케이스
즉, 지금 i, j 시작 지점이 이미 방문한 지점인지 먼저 체크해 줘야 함. 따라서 d[i] == -1 && i!=0 인 것을 추가함.

했더니 100 % 에서 틀렸습니다 가 떴다... 질문 게시판을 참고하였더니

1
0 다음과 같은 케이스에서 0 이 아닌 -1 을 내뱉는 다는 것을 깨닫았다. 즉, 시작 지점과 도착지점이 같을 경우에는 거리가 0 이어도 -1 이 아닌 0 을 내뱉어야 하는데, 내 배열에서는 -1 로 초기화를 해서 값이 다르게 나온다는 것이다.

나는 반례 찾는 거나 논리상 허점을 찾는게 왜이렇게 어려운지 모르겠다..ㅠㅠ 하면 늘겠지,,?