[BOJ 11060] 점프 점프

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

11060번: 점프 점프

 

다이나믹 프로그래밍의 본질은 기본 문제를, 여러 작은 문제들로 나눠서 해결하는 것이다.

 

 

 

 

i번째 칸까지 점프하는 최소의 값을 생각해보자.

 

 

 

 

j를 i보다 작은 수라고 가정하면, 점프가 가능하므로 j의 범위는 1 ~ i - 1이 될 수 있다.

 

 

 

 

dp[i] = dp[j] + 1

if(j + arr[j] <= i)

 

 

 

 

가 성립된다. 

 

 

 

 

하지만, 위처럼 코드를 작성하면 N * N의 시간복잡도가 발생한다.

 

 

 

 

j가 1 ~ i -1이라면 굳이 확인하지 않아도 되는 부분까지 확인이 이루어지고 있다.

 

 

 

 

dp[i + j] = dp[i] + 1(j <= arr[i])의 식으로 코드를 작성하면, dp[x] = -1인 구간은 체크하지 않아도 된다. 도달할 수 없는 곳이기 때문이다.

 

 

 

 

 

해설코드(C++).

 

#include <cstring>

#include <iostream>

 

using namespace std;

 

int N;

int dp[1001];

 

int main() {

    cin >> N;

    

    memset(dp, -1, sizeof(dp));

    dp[1] = 0;

    for(int i = 1; i <= N ;i++){

        int val;

        cin >> val;

        

        if(dp[i] == -1) continue;

        for(int j = 1; j <= val; j++){

            if(i + j <= N && (dp[i + j] == -1 || dp[i + j] > dp[i] + 1))

                dp[i + j] = dp[i] + 1;

        }

    }

    

    cout << dp[N] << endl;

    return 0;    

}