BOJ) 11060 - 점프 점프

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

11060번: 점프 점프

다이나믹 프로그래밍을 이용해 풀이하였습니다.

현재 칸 i에서 갈 수 있는 칸 j까지 최소 점프 횟수를 갱신해줍니다.

---

C++ 소스 코드

#include <iostream>
#include <algorithm>
#define MAX 1002
using namespace std;
int n;
int a[MAX],d[MAX];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    fill(&d[0], &d[MAX-1]+1,1000000);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    d[1]=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=i+a[i]&&j<=n;j++){
            d[j] = min(d[j],d[i]+1);
        }
    }
    if (d[n]==1000000){
        cout << -1 << '\n';
    }else cout << d[n] << '\n';
    return 0;
}