Algorithm/Algorithm 문제 풀이

[BAE/<JOON> 문제풀이] 11060. 점프점프

폭풍저그머성찡 2020. 5. 29. 14:24

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

 

11060번: 점프 점프

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 �

www.acmicpc.net

더보기 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> arr, dp;
    int n;
    cin >> n;
    arr.resize(n + 1);
    dp.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    dp[1] = 0;
    for (int i = 2; i <= n; i++) {
        dp[i] = 9999;
        for (int j = 1; j < i; j++) {
            if (j + arr[j] >= i) {
                dp[i] = min(dp[i], dp[j] + 1);
            }
        }
    }
    if (dp[n] == 9999) {
        cout << -1;
        return 0;
    }

    cout << dp[n];
    return 0;
}