[백준 11060] 점프 점프

문제 링크 => 11060번: 점프 점프 (acmicpc.net)

11060번: 점프 점프

---

다이나믹 프로그래밍 문제이다.

 

끝지점까지 문제에서 주어진 조건에 맞게 이동할 수 있는 경우 최소로 점프한 횟수를 반환하고

이동할 수 없는 경우 -1 를 반환한다.

 

i 번째에 점프할 수 있는 횟수를 A[i] 라고 할 때, 0 <= j <= A[i] 만큼 점프를 하도록 한다.

 

dp[x] 를 x번째로 이동하기 위한 최소 점프 횟수라고 할 때 다음과 같이 식을 세팅할 수 있다.

 

dp[i + j] = min(dp[i + j], dp[i] + 1);  

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <queue>
#include <stack>
#define endl '\n'
#define INF 1000000000
#define ll long long

using namespace std;

int N, A[1002], dp[1002];

int f() {

	fill(dp, dp + N + 1, INF);
	dp[1] = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= A[i]; j++) {
			if (i + j > N) break;
			dp[i + j] = min(dp[i + j], dp[i] + 1);
		}
	}

	return dp[N] == INF ? -1 : dp[N];
}

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

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	cout << f();

	return 0;
}