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

문제

https://www.acmicpc.net/problem/11060

11060번: 점프 점프

---

1. 마지막 풀이

사고 과정

대학 알고리즘 수업 시험 문제였으면서, 자력으로 풀어 A+를 받게 해준 고마운 문제. 그래서 더 인상깊게 남은 문제다.

 

DP엔 크게 탑다운(정답 칸부터 점화식 계산 시작, 구한 적 없다면 재귀적으로 계산) 방식과 바텀업(가장 작은 칸부터 순차적으로 점화식을 계산, 정답 칸이 계산되면 반환하며 종료) 방식이 있다.

 

문제의 구조 상 숫자가 큰 칸에서, 자신에 올 수 있는 작은 칸을 역추적하는 방식은 매우 어렵다. 그러니 자연스레 바텀업 방식을 생각하게 된다.

 

바텀업을 쉽게 구현하려면, 가장 작은 칸부터 시작해, 내가 갈 수 있는 모든 곳에 정답을 적어두는 방식이라 생각하면 편하다.

 

0	1	2	3	4	5	6	7	8	9
1	2	0	1	3	2	1	5	4	2

 

예제 1번은 이런 형태다. 윗줄은 인덱스, 아래쪽은 해당 칸에서 가능한 점프 수.

 

이에 대응하는 DP 배열을 만들어보자.

 

0	1	2	3	4	5	6	7	8	9
-1	-1	-1	-1	-1	-1	-1	-1	-1	-1

 

인덱스는 자연스레 칸의 인덱스가, 그 내용은 정답으로 출력해야 할 최소 점프 수가 된다.

 

처음엔 0으로도, -1로도, 혹은 최댓값 이상의 큰 값(최소로 갱신되므로)을 할 수도 있지만, 도달 불가 시 -1을 출력해야 하므로 -1로 초기화 했다.

 

0번 칸은 0번의 점프로 도달할 수 있으니, 0으로 바꿔준다.

 

0	1	2	3	4	5	6	7	8	9
0	-1	-1	-1	-1	-1	-1	-1	-1	-1

 

이제, 0번째 칸부터 점프를 해보자. 0칸은 1번 점프 가능하니, 1은 0칸의 점프 횟수 + 1로 갱신된다. 이런 방식으로 4번 칸에서까지 점프해보면

 

0	1	2	3	4	5	6	7	8	9
0	1	2	2	3	4	4	4	-1	-1

 

이렇게 값이 갱신된다.

 

이후 5번 칸에서 점프를 뛰어보면, 6, 7번에 도달할 수 있게 된다. 이때 점프 횟수는 5회다.

 

하지만, 이미 6번과 7번은 4번의 점프 만으로 도달했으니, 굳이 5번이나 뛰어 도달할 필요가 없다. 그러니, 갱신하지 않는다.

 

이를 식으로 표현해보면

 

// 더 적은 점프로 도달했다면 갱신
if (dp[cur] + 1 < dp[cur + jump]) {
	dp[cur + jump] = dp[cur] + 1;
}

 

이렇게 표현할 수 있으리라.

 

이런 방식으로 끝까지 코드를 동작시켜보자.

 

코드

#include <iostream>
#include <vector>

int main() {
	// 입력
	int length;
	std::cin >> length;

	std::vector<int> jump_chance(length);
	for (int i = 0; i < length; i++) {
		std::cin >> jump_chance[i];
	}

	// 계산
	std::vector<int> dp(length, -1);
	dp[0] = 0;

	for (int cur = 0; cur < length; ++cur) {
		// 도달할 수 없는 칸이 있다면 종료
		if (dp[cur] == -1) {
			break;
		}

		for (int jump = 1; jump <= jump_chance[cur] && cur + jump < length; ++jump) {
			// 아직 도달한 적 없다면 갱신
			if (dp[cur + jump] == -1) {
				dp[cur + jump] = dp[cur] + 1;
			}

			// 더 적은 점프로 도달했다면 갱신
			else if (dp[cur] + 1 < dp[cur + jump]) {
				dp[cur + jump] = dp[cur] + 1;
			}
		}
	}

	std::cout << dp[length - 1];
}

 

결과

참 오래도 포스팅을 미뤄뒀다.

매우 빠르게 통과할 수 있다.

---

가장 효율적인 코드

내 코드와 비교

https://www.acmicpc.net/source/2966163

현재 기준 3위에 위치하신 hokma님의 코드. 알고리즘은 완전히 동일하지만, 약간의 차이가 난다.

 

1. 초기 값을 나는 -1로, 이 분은 9999로 하셨다. (사실 최댓값을 생각해보면, 100,001 정도가 적당해보인다.)
2. 그 대신, 출력에서 9999인지 검사 후, 9999라면 도달하지 못 했다 상정하고 -1을 출력하셨다.

여기엔 각각 장단이 있는데,

 

장점: DP 배열을 채울 때, if문을 한 번만 검사한다. 그만큼 효율적이다.

단점: 정답이 9999인 경우 -1을 출력한다.

 

즉 속도 면에서 미미한 효과를 보고, 코드가 틀릴 가능성을 내포한 방식. 불안정한 코드기에, 나는 내 방식을 더 선호한다.

---

강평

나름 추억이 있는 문제. 이 문제를 시험에서 풀어내고 내가 성장했음에 얼마나 뿌듯해 했었는지. 영원히 내겐 추억으로 남을 문제다.