11060. 점프 점프

문제링크 : https://www.acmicpc.net/problem/11060

< 입력 >

칸 수(1<=N<=1,000)

각 칸의 점프 가능 칸 수 (0<=Ai<=100)

< 출력 >

끝 칸에 도달하기 위한 최소 점프 수

< 풀이 >

첫 칸의 dp값을 1로 초기화한 뒤 다음 칸들을 돌아보며

현재 칸(i)보다 이전의 칸(j) 중 점프해서 현재 칸에 도달할 수 있는 (arr[j] + j >= i) 칸에 있는 값들에서

+1한 값의 최솟값을 저장한다.

만약 이전 칸을 모두 확인하였음에도 값이 바뀌지 않는다면 현재 칸에 도달할 수 없다는 뜻 !

그렇게 마지막 칸까지 진행해서 마지막 칸을 출력하면 끝나는 문제.

---

- 소스 코드 -

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main(void){
    int dp[1105]={0};
    int arr[1105]={0}; // Ai가 최대 100이므로 혹시 몰라서 일단 100칸 더
    fill_n(dp,1105,1001);
    // dp배열은 최솟값을 구해야 하므로 최대 점프횟수인 1001로 초기화
    int n;
    cin>>n;
 
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
 
    // n이 1개가 아니지만 arr[0]이 0인 경우 ( 다음 칸으로 갈 수 없음 )
    if(arr[0]==0&&n!=1){
        printf("-1");
        return 0;
    }
    // n이 1개지만 arr[0]이 0인 경우 ( 이미 처음칸이자 끝 칸에 도달함 )
    else if(arr[0]==0&&n==1){
        printf("0");
        return 0;
    }
    dp[0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            // i보다 작은 j번째 칸의 인덱스와 점프 칸 수의 합이 i보다 크거나 같은 경우
            // 즉, 점프해서 i에 도달할 수 있는 경우
            if(j+arr[j]>=i){
                // 이전에 점프해서 온 칸의 값 중 최소 점프 횟수와
                // 비교하여 최솟값을 저장
                dp[i]=min(dp[i],dp[j]+1);
            }
        }
        // 비교를 거쳤음에도 1001이 저장되어 있다면 점프해서 도달할 수 없는 칸
        // 즉, 점프가 이 부분에서 끊겼음을 의미
        if(dp[i]==1001){
            printf("-1");
            return 0;
        }
    }
    
    // 끝 칸의 dp값을 출력
    // 첫 칸을 1로 초기화하였으므로 -1하여 출력
    printf("%d",dp[n-1]-1);
 
}

---