[파이썬] 백준 2253 : 점프 (골드4)

[파이썬] 백준 2253 : 점프 (골드4)

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

---

문제

N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 한다. 이때 다음 조건들이 만족되어야 한다.

이동은 앞으로만 할 수 있다. 즉, 돌 번호가 증가하는 순서대로만 할 수 있다.
제일 처음에 점프를 할 때에는 한 칸밖에 점프하지 못한다. 즉, 1번 돌에서 2번 돌이 있는 곳으로 점프할 수 있다. 그 다음부터는 가속/감속 점프를 할 수 있는데, 이전에 x칸 점프를 했다면, 다음번에는 속도를 줄여 x-1칸 점프하거나, x칸 점프하거나, 속도를 붙여 x+1칸 점프를 할 수 있다. 물론 점프를 할 때에는 한 칸 이상씩 해야 한다.
각 돌들은 각기 그 크기가 다르고, 그 중 몇 개의 돌은 크기가 너무 작기 때문에 당신은 그러한 돌에는 올라갈 수 없다.
위와 같은 조건들을 만족하면서 1번 돌에서 N번 돌까지 점프를 해 갈 때, 필요한 최소의 점프 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N, M(0 ≤ M ≤ N-2)이 주어진다. M은 크기가 맞지 않는, 즉 크기가 작은 돌의 개수이다. 다음 M개의 줄에는 크기가 작은 돌들의 번호가 주어진다. 1번 돌과 N번 돌은 충분히 크기가 크다고 가정한다.

출력

첫째 줄에 필요한 최소의 점프 횟수를 출력한다. 만약 N번 돌까지 점프해갈 수 없는 경우에는 -1을 출력한다.

---

풀이

0. 방향성 생각

• 전형적인 2차원 DP
• 같은 노드 x라도 어떤 속도로 접근했냐에 따라서 다음의 선택지가 바뀌므로 위치 x와 속도 v로 DP 테이블을 만든다
• x번째 발판에 속도 v로 도달했을 때 최솟값을 DP에 기록하자.
• N = 10000이므로 최대 속도는 약 141이다. cf) 1+2+...+k = {k*(k+1)}/2 > N인 k를 찾는다. sqrt(20000)
• 넉넉잡아서 최대 속도를 150으로 제한하고 문제를 푼다. (메모리 차이가 크게 나지 않는다)
  

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()
N,M = map(int,input().split())
trap = set(int(input()) for _ in range(M))

• 밟지 못하는 돌은 trap에 set으로 저장한다.
  

2. 함수 정의

# dp[v][x] x번째 위치에 갈 때 속도 v로 갈 경우 최솟값
dp = [[inf]*(N+1) for _ in range(150)] # 가속도가 1인 채로 유지해서 갈 경우 k(k-1)/2 > 10000인 k
dp[0][1] = 0
if 2 not in trap:
    dp[1][2] = 1

• DP 테이블 초기화 시켜준다.
• node 1에는 속력 0으로 접근한다.
• node 2가 트랩이 아닌 경우 속도 1로 접근한다.
  

3. DP 테이블 업데이트 및 출력

for x in range(2,N): # x에
    for v in range(150): # 속도 v로 위치한 말이
        for nv in (v-1,v,v+1): # nv 속도로
            nx = x + nv # nx에 이동하는 경우
            if nx <= N and 1<=nv<150 and nx not in trap: # 돌다리 범위 / 1칸 이상 / 작은 돌멩이 x
                dp[nv][nx] = min(dp[nv][nx],dp[v][x]+1)

answer = min(dp[i][-1] for i in range(150))
print(answer if answer != inf else -1)

• nv loop를 도는 와중에 범위가 2개씩 겹쳐서 시간이 조금 더 걸렸다.
• O(3*(N**2))인데 루프문을 잘 짜면 O(N**2)까지 줄일 수 있다.
  

---

전체코드

#### 백준 2253 골드4 점프

N,M = map(int,input().split())
trap = set(int(input()) for _ in range(M))
# %%
inf = float('inf')

# dp[v][x] x번째 위치에 갈 때 속도 v로 갈 경우 최솟값
dp = [[inf]*(N+1) for _ in range(150)] # 가속도가 1인 채로 유지해서 갈 경우 k(k-1)/2 > 10000인 k
dp[0][1] = 0
if 2 not in trap:
    dp[1][2] = 1

for x in range(2,N): # x에
    for v in range(150): # 속도 v로 위치한 말이
        for nv in (v-1,v,v+1): # nv 속도로
            nx = x + nv # nx에 이동하는 경우
            if nx <= N and 1<=nv<150 and nx not in trap: # 돌다리 범위 / 1칸 이상 / 작은 돌멩이 x
                dp[nv][nx] = min(dp[nv][nx],dp[v][x]+1)

answer = min(dp[i][-1] for i in range(150))
print(answer if answer != inf else -1)

코멘트

• 맥시멈 속도 제한 150을 누락해서 삽질했다.
  • 항상 인덱스를 가지는 자료구조의 경계값 인덱스 생각하기.

• v에서 nv를 만드는 loop에서 범위가 2개씩 겹쳐서 시간이 조금 더 걸렸다.
  • 노드 중복 계산 방지하기.