[백준/C++][점프 점프(11060번)]

문제

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

11060번: 점프 점프

문제 해결

1. 그 자리에서 3을 점프뛰면 앞, 앞앞, 앞앞앞까지 탐색하는데 현재 dp의 값+1과 탐색한 자리에 dp값과 비교해서 작은 값을 선택한다.

2. 만약 그 자리가 끝이거나 넘어서면 결과값의 dp이므로 현재 자리의 dp값과 결과값dp를 비교해서 작은값이 결과값dp가 된다.

 

코드

#include <iostream>
#define infy 987654321
using namespace std;
i   nt min(int a,int b){
    if(a>b){return b;}
    else{return a;}
}
int main(void){
    int N,ary[1002],dp[1002],result = infy,temp = infy;
    cin >> N;
    for(int i = 0;i<N;i++){
        cin >> ary[i];
    }
    if(N == 1){cout << 0;}
    else{
    for(int i = 0;i<N;i++){dp[i] = infy;}
    dp[0] = 0;
    for(int i = 0;i<N;i++){
        int next = ary[i];
        for(int j = i+1;j<=i+next;j++){
            if(j>=N-1){
                temp = min(temp,dp[i]+1);
            }
            else{
                dp[j] = min(dp[i]+1,dp[j]);
            }
        }
    }
    if(temp == infy){cout << "-1";}
    else{cout << temp;}
    }
}