점프 점프

문제

백준 11060번 - 점프 점프

언어

JavaScript

순서도

1 차원 형식의 dp 배열 생성하기
점화식 생성 후 dp 배열 채우기

문제 풀이 step 1

재환이는 1 x N 크기의 미로에 갇혀있습니다.
미로는 1 x 1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있습니다.
i 번째 칸에 쓰여 있는 수를 Ai 라고 했을 때, 재환이는 Ai 이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있습니다.
예를 들어, 3 번째 칸에 쓰여 있는 수가 3 이면, 재환이는 4, 5, 6 번 칸 중 하나로 점프할 수 있습니다.
재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 합니다.
이 때, 최소 몇 번 점프해야 갈 수 있는지 구하는 문제입니다.
만약 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1 을 출력합니다.

문제 풀이 step 2

dp[k] = k 번째 칸에 도달하는데 점프한 최소 횟수
DP의 특징인 “작은 문제의 해답으로부터 큰 문제의 해답을 찾는다”를 이용합니다.
점화식은 “dp[i + j] = Math.min(dp[i + j], dp[i] + 1)” 입니다.
- i 번째 칸에서 j 만큼 점프한 칸에 도달할 때, 점프한 최소 횟수는
- 기존의 dp[i + j] 값과 dp[i] + 1 값 중에서 더 작은 값입니다.
dp 배열은 모두 -1 로 초기화합니다.
- 가장 오른쪽 끝으로 갈 수 없는 경우 -1 을 출력해야하기 때문입니다.
base 값은 0 입니다.
- 0 번 칸에서 시작하기 때문입니다.
점화식과 base 값을 이용해서 dp 배열을 채웁니다.
- 예를 들어, 0 번째 칸에 쓰여있는 정수가 3 이라 가정하겠습니다.
  - 0 번째 칸에서 갈 수 있는 칸은 1, 2, 3 번 칸 중 하나로 점프할 수 있습니다.
  - 그렇다면, dp[1] 은 기존에 1 번째 칸에 도달하기 위해 점프한 최소 횟수인 “dp[1]” 과 dp[0] 에서 한 번 점프하는 “dp[0] + 1” 중에서 최소인 값으로 결정됩니다.
  - 마찬가지로 dp[2], dp[3] 도 동일한 방식으로 결정됩니다.
dp 배열을 모두 채웠으면, 마지막 칸에 도달하는데 점프한 최소 횟수인 dp[n - 1] 을 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

후기

여태까지 풀었던 DP 문제와 다른 방식의 문제였습니다.
일반적으로 DP 문제는 현재의 값을 정하기 위해서 이전의 값들을 이용하고 다음 값으로 넘어가는 방식인데,
이번 DP 문제에서는 현재의 값을 이용해서 이후의 값들을 정하고 다음 값으로 넘어가는 방식이었습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const n = Number(input[0]);
	const arr = input[1].split(" ").map(Number);

	// dp 배열 -1 로 초기화
	const dp = Array(n).fill(-1);

	// base
	dp[0] = 0;

	// dp 배열 채우기
	for (let i = 0; i < n; i++) {
		// i 번째 칸의 dp 값이 -1 이라는 의미는 i 번째 칸에 도달하는 경우가 아예 없다는 뜻
		// 이 말은 곧, i 의 오른쪽의 칸들도 전부 갈 수 없다는 뜻
		// 이유는 점프할 때 칸에 쓰여있는 정수 이하의 수만큼 점프하기 때문
		if (dp[i] === -1) break;

		for (let j = 1; j <= arr[i]; j++) {
			// n 을 넘어가는 경우는 모두 제외
			if (i + j >= n) break;

			// i + j 번째 칸으로 도달하는 방법이 없었다면 비교할 필요 없이 dp[i] + 1 로 설정
			if (dp[i + j] === -1) dp[i + j] = dp[i] + 1;
			// i + j 번째 칸으로 도달하는 방법이 있었다면, 비교 후 최소값으로 설정
			else dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
		}
	}

	// 가장 오른쪽 칸에 도달하기위해 점프한 최소 횟수 반환
	return dp[n - 1];
};

console.log(solution(input));