171208_11060_점프 점프

//https://www.acmicpc.net/problem/11060 #include <iostream>

using namespace std;

int main()

{

int N;

cin >> N;

int A[1001];

int dp[1001];

int min;

for(int i=1; i<=N; i++) cin >> A[i];

dp[1]=0;

for(int i=2; i<=N; i++)

{

min=1001;

for(int j=i-1; j>0; j--)

{

if(i-j==101) break;

if(j+A[j]>=i && dp[j]!=-1)

if(min>dp[j]+1) min=dp[j]+1;

}

if(min==1001) dp[i]=-1;

else dp[i]=min;

}

cout << dp[N];

}

for문을 나오는 조건을 

i-j==99로 해서 괜히 헤맸다ㅠ-ㅠㅎㅎ

i로 이동해 올 수 있는 수들에 대해 탐색해서 dp[i]가 최소인 값 찾는 방법 이용

-> i로 이동해 올 수 있는 값들을 j라고 한다면, i-100부터 i-1까지가 j의 범위, 또는 i가 100보다 작은 경우에는 1번 칸까지 탐색하면 됨.

(ex i가 104 라면 A[4]=100 일 경우 이동 가능, 즉 4~103까지 탐색 범위가 됨

탐색 범위 i=104, j는 3이면 더이상 탐색할 필요가 없음. 따라서 i-j==101이면 break)

-> 탐색 조건 

1. j+A[j]가 i 이상이어야 함 j에서 A[j]이하의 값만큼 이동한 위치가 i!!

2. dp[j]가 도달 가능한 점 이어야함. 

min=1001로 정해두고 탐색이 다 된 시점에서 min값의 변동이 없다면 닿을 수 없는 지점임을 이용.