BOJ #11060 - 점프 점프

https://icpc.me/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;
}