[BOJ] 11060 점프 점프

점프 점프

1*n 크기의 배열
점프는 i번째 칸의 숫자 이하의 횟수만큼 점프 가능

동전 줍기 문제랑 비슷 ->  dp?

dp로 각 i번째까지 갈 수 있는 방법 중 최소 점프 횟수 확인

---

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n; cin>> n;
    int arr[1002], dp[1002];
    for(int i=0; i<n; i++){
        cin >> arr[i];
        dp[i] = 100000;
    }
    dp[0] = 0;
    for(int i = 0; i< n; i++){  //처음부터 끝까지
        for(int j =1; j <= arr[i]; ++j){ // 1 ~ arr[i] 만큼 점프한걸 다 비교
            if(i + j >= n){ //마지막까지 갔거나 넘어가면 마지막에 도달 가능
                break;
            }
            if(dp[i+j] > dp[i] + 1){   //다음 자리의 결과 보다 크다
                dp[i+j] = dp[i] + 1;    // 다음 자리의 결과 dp에 저장
            }
        }
    }
    if(dp[n-1] == 100000){	//도달 불가
        dp[n-1] = -1;
    }
    cout << dp[n-1];
}