백준 11060 - 점프 점프 (c++)

백준 11060 - 점프 점프

문제 링크

생각 및 접근

• 각 칸에 오른쪽으로 얼마나 갈 수 있는지 적혀있고, 그 규칙대로 마지막 칸까지 도달했을 때, 최소 몇 번 점프해야 갈 수 있는지 구하는 문제다.
• int dp[i]
  • i번째 칸에 왔을 때, 최소 몇 번 점프해서 왔는지 기억하는 배열
• 초기 dp는 int의 최댓값으로 잡는다. 점프 수의 최솟값을 구하기 위함이다.
• dp 과정

    // 맨 첫 칸은 점프를 하지 않았으므로 0
    dp[1] = 0;
    for(int i = 1; i < n; i++){
        // j : i번째 칸에서 점프해서 갈 수 있는 칸(j)에 대해서 최소 점프 수 검사.
        for(int j = i + 1; j <= min(arr[i] + i, n); j++){
            dp[j] = min(dp[i] + 1, dp[j]);
        }
    }

코드

#include <bits/stdc++.h>
using namespace std;

int n, arr[1001], dp[1001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        dp[i] = 2147000000;
    }

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

    if(dp[n] == 2147000000) cout << -1;
    else cout << dp[n];
}

채점