백준 #11060 점프 점프


BOJ #11060 - 점프 점프

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

# 문제 분류

Dynamic Programming

풀이 접근 방법


  1. 칸에 있는 수만큼 오른쪽 칸들을 보고 dp[current]에 1을 더해서 dp[jumped]에 넣으면 된다.
  2. 단순하네!
  3. 점화식은 dp[current+jump] = min(dp[current+jump], dp[current] + 1)이다.

맨 처음 dp 배열 초기화할 때 INF로 설정해주고, 만약 dp[N-1]이 INF라면 도달할 수 없는 것이므로 -1을 출력한다.

소스 코드


#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <vector>

using namespace std;

int N;
int INF = 1e9;
int arr[1200], dp[1200];

int main(){
    scanf("%d", &N);

    for(int i=0; i<N; i++){
        int tmp;
        scanf("%d", &tmp);
        arr[i] = tmp;
    }

    for(int i=0; i<1200; i++) dp[i] = INF;
    dp[0] = 0;

    for(int i=0; i<N; i++){
        int current = arr[i];
        for(int j=1; j<=current; j++){
            dp[i+j] = min(dp[i+j], dp[i]+1);
        }
    }

    if(dp[N-1] == INF){
        printf("-1");
    }
    else{
        printf("%d", dp[N-1]);
    }

    return 0;
}