[백준][11060번][DP] 점프 점프

점프점프

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

<문제>

<코드>

#include <stdio.h>
 
int main() {
    
    int N;
    int Dp[1001]={0,};
    Dp[1]=1;
    scanf("%d",&N);
    
    for(int i=1;i<=N;i++){
        int num;
        scanf("%d",&num);
        
        if(Dp[i]==0)
            continue;
            
        for(int j=1;(j<=num) && (i+j<=1000);j++){
            if(Dp[i+j]>Dp[i]+1 || Dp[i+j]==0)
                Dp[i+j]=Dp[i]+1;
        }        
    }    
    
    if(Dp[N]==0)
        printf("-1\n");
    else
        printf("%d\n",Dp[N]-1);
 
    return 0;
}

<문제 푼 요령>

 1. 이 문제의 점화식은 현재의 값에 따라서 다음 값을 채워나가고 그 채워나갈때 최소값만 채워서 나가면 된다. 

 2. 즉 Dp[now+jump] = Min( Dp[now+jump] , Dp[now] +1 ) 값이 되는 것이다. 

 3. 단 여기서 조건은 무조건 출발은 왼쪽 끝이기 때문에 왼쪽끝을 1로 두고 0에서 시작한 경우는 아예 갈 수 없는 경우라고 정의 하면된다.

 4. 그리고 최소값 비교할때 0은 비교할 필요가 없기 때문에 Dp[now+jump] 가 0일 시는 Dp[now] +1 을 대입해 주면된다.

 5. 즉 이렇게 구한값에서 Dp[N] 이 0이라면 이 경우는 왼쪽 끝에서 오른쪽 끝으로는 갈 수 없는 경우이기 때문에 -1을 출력해 주면 된다.