[C++] 백준 11060번 점프 점프

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

1*N의 미로에서 칸마다 입력되어 있는 숫자만큼 점프 할 수 있습니다.
이 때 N의 위치까지 최소 몇번으로 갈 수 있는지 찾는 문제입니다.

for문을 통해 1~N까지 반복할 때
DP[i]에서 i는 위치이고,
i의 위치까지 왔을 때 최소한의 횟수를 저장합니다.

DP[i] == 0 일 때는 i의 위치까지 올 수 없는 경우이므로 for문을 종료해줍니다.

DP[i + j]는 현재 위치에서 점프 할 수 있는 곳입니다.
현재 계산중인 횟수 +1 보다 DP[i + j]에 저장된 값이 적거나
DP[i + j]에 아직 아무것도 쓰여지지 않은 상태이면
DP[i + j] 에 DP[i] + 1을 대입해줍니다.

DP[N]이 0이면 불가능 한 경우이므로 -1을 출력하고
그렇지 않으면 DP[N]을 출력해 줍니다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int DP[1010] = { 0, };

int main(int argc, char *argv[])
{
	int N;

	cin >> N;

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

		if (DP[i] == 0) {
			break;
		}

		for (int j = 1; j <= num; ++j) {
			if (i + j > 1000) {
				break;
			}
			if (DP[i + j] > DP[i] + 1 || DP[i + j] == 0) {
				DP[i + j] = DP[i] + 1;
			}
		}
	}

	if (DP[N] == 0) {
		cout << -1 << endl;
	}
	else {
		cout << DP[N] - 1 << endl;
	}

	return 0;
}