[정글 알고리즘] - [중] 백준2253- 점프- 골드4

 

상태 정의와 경로 감각이 중요해서 상태 중심으로 풀어 쓴 상세형 버전이다.

1. 문제를 아주 짧게 말하면

1번 돌에서 N번 돌까지 앞으로만 이동한다. 이전 점프 길이를 기준으로 다음 점프 길이는 -1, 0, +1만 바꿀 수 있고, 몇몇 돌은 밟을 수 없다. 목표는 최소 점프 횟수다. [Source](https://www.acmicpc.net/problem/2253)

2. 핵심 아이디어

상태를 두 개로 잡아야 한다

현재 돌 번호만 알면 부족하다. 직전에 몇 칸을 뛰었는지도 알아야 다음 점프 후보가 정해지기 때문이다.

dp[i][v] = i번 돌에 마지막 점프 길이 v로 도착했을 때의 최소 점프 횟수

3. 전체 코드

1import sys

2

3input = sys.stdin.readline

4INF = 10 ** 9

5

6n, m = map(int, input().split())

7small = {int(input()) for _ in range(m)}

8

9max_jump = int((2 * n) ** 0.5) + 2

10dp = [[INF] * (max_jump + 2) for _ in range(n + 1)]

11dp[1][0] = 0

12

13for i in range(2, n + 1):

14 if i in small:

15 continue

16

17 for v in range(1, max_jump + 1):

18 prev = i - v

19 if prev < 1:

20 break

21

22 dp[i][v] = min(dp[prev][v - 1], dp[prev][v], dp[prev][v + 1]) + 1

23

24answer = min(dp[n])

25print(answer if answer < INF else -1)

4. 코드 한 줄씩 설명

줄	코드	설명
3	input = sys.stdin.readline	빠른 입력을 위한 설정이다.
4	INF = 10 ** 9	도달 불가능 상태를 표현하기 위한 큰 값 INF를 만든다.
6	n, m = map(int, input().split())	돌 개수 n과 작은 돌 개수 m을 입력받는다.
7	small = {int(input()) for _ in range(m)}	밟을 수 없는 작은 돌 번호들을 집합으로 저장해 빠르게 검사한다.
9	max_jump = int((2 * n) ** 0.5) + 2	점프 길이는 대략 sqrt(2n) 정도까지만 보면 충분해서 상한을 잡는다.
10	dp = [[INF] * (max_jump + 2) for _ in range(n + 1)]	dp[i][v]는 i번 돌에 마지막 점프 길이 v로 도착했을 때의 최소 점프 횟수다.
11	dp[1][0] = 0	1번 돌에서 아직 점프하지 않은 시작 상태를 0으로 둔다.
13	for i in range(2, n + 1):	2번 돌부터 n번 돌까지 차례대로 계산한다.
14	if i in small:	작은 돌이면 애초에 설 수 없으므로 건너뛴다.
17	for v in range(1, max_jump + 1):	가능한 마지막 점프 길이 v를 모두 시도한다.
18	prev = i - v	현재 i번 돌에 길이 v로 왔다면 직전 돌은 i-v다.
19	if prev < 1:	직전 돌 번호가 1보다 작아지면 더 볼 필요가 없다.
22	dp[i][v] = min(dp[prev][v - 1], dp[prev][v], dp[prev][v + 1]) + 1	직전 점프 길이는 v-1, v, v+1 중 하나였을 수 있으므로 그 셋의 최소값에 1을 더한다.
24	answer = min(dp[n])	n번 돌에 도착한 여러 상태 중 최소 점프 횟수를 찾는다.
25	print(answer if answer < INF else -1)	여전히 INF면 도달 불가능이므로 -1을 출력하고, 아니면 최소 횟수를 출력한다.

5. 돌 배치 시각화

이해용 예시로 문제 설명에 자주 등장하는 N=19, 작은 돌 6, 11, 16 상황을 그려보면 다음과 같다.

1

시작

2

 

3

 

4

 

5

 

6

작은 돌

7

 

8

 

9

 

10

 

11

작은 돌

12

 

13

 

14

 

15

 

16

작은 돌

17

 

18

 

19

도착

6. 상태와 점화식 감각 잡기

상태 정의

dp[i][v] = i번 돌에 마지막 점프 길이 v로 도착했을 때의 최소 점프 횟수

점화식 감각

i번 돌에 길이 v로 왔다면 직전 위치는 i-v다. 직전 점프 길이는 v-1, v, v+1 중 하나였을 수 있다.

예시 경로 해석

위 경로는 하나의 이해용 예시다. 실제 코드는 모든 가능한 상태를 DP로 검사해 최소 점프 횟수를 찾는다.

7. 이해용 경로 추적

아래는 한 가지 이해용 경로다. 실제 코드는 모든 상태를 검사해서 최소 횟수를 찾는다.

점프 1: 1번 돌 → 2번 돌

이번 점프 길이 = 1. 이전 점프 길이를 기준으로 -1, 0, +1만 가능하므로 이 상태를 (현재 돌=2, 직전 점프=1)로 관리한다.

점프 2: 2번 돌 → 4번 돌

이번 점프 길이 = 2. 이전 점프 길이를 기준으로 -1, 0, +1만 가능하므로 이 상태를 (현재 돌=4, 직전 점프=2)로 관리한다.

점프 3: 4번 돌 → 7번 돌

이번 점프 길이 = 3. 이전 점프 길이를 기준으로 -1, 0, +1만 가능하므로 이 상태를 (현재 돌=7, 직전 점프=3)로 관리한다.

점프 4: 7번 돌 → 9번 돌

이번 점프 길이 = 2. 이전 점프 길이를 기준으로 -1, 0, +1만 가능하므로 이 상태를 (현재 돌=9, 직전 점프=2)로 관리한다.

점프 5: 9번 돌 → 12번 돌

이번 점프 길이 = 3. 이전 점프 길이를 기준으로 -1, 0, +1만 가능하므로 이 상태를 (현재 돌=12, 직전 점프=3)로 관리한다.

점프 6: 12번 돌 → 15번 돌

이번 점프 길이 = 3. 이전 점프 길이를 기준으로 -1, 0, +1만 가능하므로 이 상태를 (현재 돌=15, 직전 점프=3)로 관리한다.

점프 7: 15번 돌 → 19번 돌

이번 점프 길이 = 4. 이전 점프 길이를 기준으로 -1, 0, +1만 가능하므로 이 상태를 (현재 돌=19, 직전 점프=4)로 관리한다.

8. 자주 헷갈리는 포인트

• 직전 점프 길이는 현재 v에서 거꾸로 보면 v-1, v, v+1 세 가지다.
• 작은 돌은 무조건 스킵해야 한다.
• 최소 점프 문제라서 도달 불가능 상태는 INF 같은 큰 값으로 관리하는 것이 편하다.

9. 복잡도

점프 길이 상한을 약 √N 수준으로 보면 시간 복잡도는 대략 O(N√N) 이다.

공간 복잡도도 같은 수준의 DP 테이블 때문에 O(N√N) 이다.

원문 문제 링크

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