11060번: 점프 점프

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


$O(na)$

i번째 칸에 도달 가능한 경우 i+1~i+a[i] 번째 칸에 도달하는데 필요한 최소 칸수를 갱신해준다.

#include<cstdio>
int n, dp[1000] = { 1 };
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        if (dp[i]) for (int j = i + 1; j <= i + x && j<n; j++) if (!dp[j] || dp[j]>dp[i] + 1) dp[j] = dp[i] + 1;
    }
    printf("%d", dp[n - 1] - 1);
    return 0;
}