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

문제

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

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

 

입력

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

 

출력

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

 

코드

#include <iostream>

using namespace std;

int N;
int maze[1001];
int jump[1001];

int main()
{
	int i;
	int j;
    
	cin >> N;
	if (N < 1 || N > 1000)
	{
		return -1;
	}
	for (i = 1; i <= N; i++)
	{
		cin >> maze[i];
	}
	jump[1] = 1;
    for (i = 1; i <= N; i++)
	{
        if (jump[i] == 0)
            continue;
        for (j = 1; j <= maze[i]; j++)
		{
			if (i + j > N)
				break;
            if (jump[i + j] == 0 || jump[i + j] > jump[i] + 1)
                jump[i + j] = jump[i] + 1;
        }        
    }
    if(jump[N])
		cout << jump[N] - 1 << endl;
	else
        cout << -1 << endl;
	return 0;
}

 

처음 위치부터 시작하여 각 위치에 이르기 위한 점프 횟수의 최솟값을 저장한다. 마지막 위치에 이르기 위한 점프 횟수가 0이면 마지막 위치에 도달하지 못한다는 것을 의미한다. 도달한 경우, 처음 위치에서 0이 아닌 1로 시작하기 때문에 마지막 위치의 (점프 횟수 - 1)이 정답이 된다. 처음 위치에서 1로 시작하는 것은 처음 위치인 경우에 대해 따로 처리하지 않고, 다른 위치들과 동일한 코드를 적용하기 위해서다.

 

링크

11060번: 점프 점프

inbdni/Baekjoon