[백준] 11060번. 점프 점프

[백준] 11060번. 점프 점프

1. 문제

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

2. 입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

3. 출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

4. 풀이

• DP를 이용하였다.
• 각 단계에 이동할 수 있는 수를 저장한 arr 배열과 현재 단계까지 오는 최소 횟수를 저장한 d배열
• 끝에 정확히 도착하는 것이 아니라 끝을 넘어가기만 하면 되기 때문에 i+j >= n 인 경우와 그렇지 않은 경울르 따로 처리

5. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[1000];
int d[1000];
int n;

void init_arr(int length) {
	for (int i = 1; i < length; i++){
		d[i] = 9999;
	}
}

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

	cin >> n;

	for (int i = 0; i < n; i++){
		cin >> arr[i];
	}
	init_arr(n);
	d[0] = 0;
	for (int i = 0; i < n; i++){
		int step = arr[i];
		for (int j = 1; j <= step; j++){
			if (i + j >= n) d[n - 1] = min(d[n-1], d[i] + 1);
			else d[i + j] = min(d[i + j], d[i] + 1);
		}
	}
	if (d[n - 1] >= 9999) cout << -1;
	else cout << d[n - 1];
}