11060

백준 11060번

Link: 11060번: 점프 점프

---

문제 설명

역시 DP문제다.

옆에서 친구가 풀던 문제여서 한번 풀어봤는데, 앞에서 풀었던 문제에서 찾아낸 규칙과 유사한 규칙으로 풀린다는 점을 알아냈다.

될까 해서 돌려보니 역시 성공.

이번에도 코드는 정말 짧다.

하루에 DP를 2문제나 풀어내다니 내 자신이 살짝 놀랍다.

이런식으로 DP에 대한 두려움을 좀 없앨 수 있으면 좋겠다.

---

정답 코드

//
// Created by Keith_Lee on 26/02/2019.
//

#include <iostream>
#include <vector>
#include <strings.h>

using namespace std;

int N;

int map[1001];
int DP[1001];

int min(vector<int> v){
    int result = 99999;

    for(int i=0; i<v.size(); i++){
        if(result > v[i]){
            result = v[i];
        }
    }

    return result;
}

int main(){
    bzero(DP, sizeof(DP));
    bzero(map, sizeof(map));
    cin >> N;

    for(int i=1; i<=N; i++){
        cin >> map[i];
    }

    for(int i=2; i<=N; i++){
        vector<int> temp;

        for(int j=1; j<i; j++){
            if(j + map[j] >= i){
                temp.push_back(DP[j] + 1);
            }
        }

        DP[i] = min(temp);
    }

    if(DP[N] == 99999){
        DP[N] = -1;
    }

    cout << DP[N] << '\n';

    return 0;
}

---