[백준] 알고리즘 11060번 - 점프 점프 문제

문제

www.acmicpc.net/problem/11060

11060번: 점프 점프

소스코드

#include <bits/stdc++.h>
using namespace std;
int arr[1001];
int dp[1001];
int n;
void res(int x) {

    for (int i = x + arr[x]; i >= x + 1; i--) {
        if (i<=n){
            if (dp[i]==-1 || dp[i] > dp[x] + 1) {
                dp[i] = dp[x] + 1;
                res(i);
            }
        }
    }
}
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] = -1;
    }
    dp[1] = 0;
    res(1);
    cout << dp[n];
}

풀이

모든 범위의 수를 검사해보는데, dp[i]>dp[x]+1이 성립할때만 검사하여, 모든 경우의 수를 검사하지 않고 필요한 부분들만 검사하게된다.

 

인덱스의 범위를 초과하면 자동으로 다음 문으로 넘어간다.

 

이부분이 이문제의 핵심인거 같다.