백준 11060 점프 점프

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

쉬운 DP 문제입니다. memoization 배열에 최소 점프 횟수를 저장하고, 현재 지점에 올 수 있는 모든 지점을 검사하면 됩니다.

#include<bits/stdc++.h>
using namespace std;
const int SZ=1005;
int arr[SZ];
int memo[SZ];
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	for(int i=1;i<=n;i++) cin>>arr[i];
	memset(memo,-1,sizeof(memo));
	memo[1]=0;
	for(int i=2;i<=n;i++){
		int ans=n+5;
		for(int j=1;j<=min(100,i-1);j++){
			if(arr[i-j]>=j && memo[i-j]!=-1) ans=min(ans,memo[i-j]+1);
		}
		if(ans!=n+5) memo[i]=ans;
	}
	cout<<memo[n];
	return 0;
}