[BOJ] 11060번. 점프 점프

www.acmicpc.net/problem/11060

11060번: 점프 점프

이 문제 진짜 어렵더라구요... 저도 해설 보고 풀었습니다. 근데 해설들이 하나같이 참 대충이더라구요...

 

DP의 길은 참 멀고도 먼 것 같습니다.

 

[정답 코드 보기]

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
using namespace std;

int main()
{
	int n;
	int field[1500] = { 0, };
	int dp[1500] = { 0, };
	
	cin >> n;
	for (int i = 0; i < n; i++)	cin >> field[i];
	for (int i = 1; i <= n; i++) dp[i] = 100000;

	if (field[0] == 0 && n > 1)
	{
		cout << -1;
		return 0;
	}
	if (field[0] == 0 && n == 1)
	{
		cout << 0;
		return 0;
	}

	dp[0] = 1;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (j + field[j] >= i)
			{
				dp[i] = min(dp[i], dp[j] + 1);
			}
		}
	}

	if (dp[n-1] == 100000) cout << -1;
	else cout << dp[n-1]-1;
	return 0;	
}

 

[코드 설명 보기]

우선, 초기화 및 변수를 선언해줍니다. dp의 각 배열은 아주 큰 수 100000으로 초기화했습니다.

int main()
{
	int n;
	int field[1500] = { 0, };
	int dp[1500] = { 0, };
	
	cin >> n;
	for (int i = 0; i < n; i++)	cin >> field[i];
	for (int i = 1; i <= n; i++) dp[i] = 100000;

그런데... 맨 앞이 0인 경우에 항상 점프의 결과가 -1이 아니라는거.... 눈치채셨을까요???

맨 앞이 0이고, n이 1일 경우, 점프를 안 해도 되므로 결과는 0입니다.

맨 앞이 0인데 n이 2 이상일 경우, 점프를 해서 도착점에 닿아야 하므로 결과는 -1입니다.

	if (field[0] == 0 && n > 1)
	{
		cout << -1;
		return 0;
	}
	if (field[0] == 0 && n == 1)
	{
		cout << 0;
		return 0;
	}

자! 그럼 쭉정이들을 걸러냈으니 본격적으로 DP를 시작해보겠습니다.

제가 하고 싶은 것은 다음과 같습니다.

 

 

 입력 후 초기 상태는 다음과 같습니다.

 

입력: 1 2 0 1 3 2 1 5 4 2

[field 상태]

1

2

0

1

3

2

1

5

4

2

[dp 상태]

1

100000

100000

100000

100000

100000

100000

100000

100000

100000

현재 탐색하고 있는 위치 i가 있습니다. 

0부터 i까지 탐색하는 j가 있습니다. 

코드를 먼저 보겠습니다.

dp[0] = 1;
for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (j + field[j] >= i)
			{
				dp[i] = min(dp[i], dp[j] + 1);
			}
		}
	}

i가 0일 때는 두 for문에서 할 게 없으므로 넘어가겠습니다.

i가 1인 경우 j는 0부터 i까지 탐색을 시작합니다.

 

가장 최소의 점프로 멀리 가려면, 점프를 아끼면서 최대한 멀리멀리 가는 경우를 찾아야 합니다. 

그러니까 i와 j를 다르게 설정한 이유는 다음과 같습니다.

 

[i위치까지 최소한의 점프로 가려고 하는데, j로 0부터 i까지 최소한의 경우로 가는 경우를 찾으면서 가자!!]

 

따라서 위 코드의 if 부분을 뜯어보죠.

if (j + field[j] >= i)

j는 현재 위치고 field[j]는 점프 가는 범위입니다. 현재 위치(j)에서 최대 점프 가능 범위(field[j])를 합한 것이 i위치를 넘어간다면, 일단 j위치는 일단 멀리 갈 수 있는 점프의 범위라고 생각할 수 있습니다. 

일단 멀리 갈 수 있는 점프의 범위를 찾았다고 해서 우리의 할 일이 끝난 것은 아닙니다. 이전에 더 멀리 가는 점프가 있었을 수도 있겠죠!!

예를 들어보겠습니다.

i가 3일 때 다음과 같은 상황이 있겠습니다.

따라서 우리는 DP를 이용합니다. 각각의 인덱스는 처음에 100000으로 초기화되어있기 때문에, 처음 들어온 수는 제대로 잘 들어올 것입니다.

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

dp[i]는 그냥 가만히 있는 경우, dp[j]+1은 j에서 점프를 한번 해주는 경우입니다.

둘을 비교해서 더 작은 경우가 dp[i]에 들어가면 되겠습니다.

 

n까지 탐색이 끝나면 결과물을 출력합니다.

dp[n-1]이 아직 초기화 후 100000이라면 점프를 통해 닿지 못했단 뜻이므로 -1을 출력해줍니다.

그렇지 않다면, 애초에 dp[0]=1로 초기화했었기 때문에 1을 뺀 숫자를 출력해줍니다.

	if (dp[n-1] == 100000) cout << -1;
	else cout << dp[n-1]-1;
	return 0;	
}