(c++)백준 11060번: 점프 점프

www.acmicpc.net/problem/11060

11060번: 점프 점프

[풀이]

DP로 풀 수 있는 문제!

DP[i] : i번째 칸에서 최소 몇 번 점프해야 N번째 칸에 갈 수 있는지

주어진 칸이 한 칸일 경우, 한 번만 점프해서 N번째 칸에 갈 수 있는 경우, 점프할 수 없는 칸인 경우를 모두 신경써줘야 한다.

#include <iostream>
#include <cstring>//memset
using namespace std;

int N;
int Maze[1001];
int DP[1001];

void solution() {
	memset(DP, -1, sizeof(DP));
	//칸이 한 개일 때
	if (N == 1) {
		cout << 0 << '\n';
		return;
	}
	for (int i = N - 1; i >= 1; i--) {
		//한 번 점프해서 갈 수 있는 경우
		if (Maze[i] + i >= N)
			DP[i] = 1;
		//점프할 수 없는 칸인 경우
		else if (Maze[i] == 0)
			continue;
		else{
			int Min = 1000000;
			for (int j = 1; j <= Maze[i]; j++) {
				if (DP[i + j] < Min && DP[i + j] != -1) 
					Min = DP[i + j];
			}
			if (Min == 1000000)
				DP[i] = -1;
			else
				DP[i] = Min + 1;
		}
	}
	cout << DP[1] << '\n';
}

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