[PYTHON] 백준 2253 - 외판원 순회

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

성능 요약

메모리: 138348 KB, 시간: 236 ms

분류

다이나믹 프로그래밍

문제 설명

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

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

위와 같은 조건들을 만족하면서 1번 돌에서 N번 돌까지 점프를 해 갈 때, 필요한 최소의 점프 횟수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

---

아이디어, 문제풀이

• dp를 2차원 배열로 설정 했을때, 뭘 축으로 두고 저장할지를 생각해 봐야 한다.
• 나는 점프한 거리를 한 축으로 지정, 다른 축은 돌맹이의 위치로 지정했다. 거의 visit과 같은 역할을 한다.

---

TROUBLE SHOOTING

• 일단 아이디어를 생각한 뒤는 생각보다 쉬웠다. 코드 구현이 막히는 곳은 없었다. 문제는 메모리 초과였다.

• dp는 그자체로 시간복잡도를 줄이기 위해서 존재하는데, 내가 처음 푼 방식은 완전탐색과 다름 없었다. dp를 적용했으니, 완전탐색의 범위를 최대한 좁혀 메모리 초과를 해결하는 방식으로 문제 풀이를 진행했다.

  max_speed = int((2 * n) ** 0.5) + 1
  
  dp = [[float('inf')] * (max_speed+1) for _ in range(n+1)]
  dp[1][0] = 0
  
  def fun():
  
      for i in range(1, n+1):
          stone = i
  
          if stone in n_list:
              continue
  
          for j in range(1, max_speed):

  핵심은 max_speed라는 변수였는데, 나는 기존에 쓴 코드에서, 점프를 0부터 i까지 가능하도록 설계했다. 점프는 1+2+3+4+5 와 같은 방식으로, 14번째는 최대 점프거리가 5다. max_speed = int((2 * n) ** 0.5) + 1 수식으로 표현하면 이런 값이 나오고, 효과적으로 메모리를 단축시킬수 있다.
  

• 그 외에는 문제없이 풀이가 가능했다. min_jumps = min(dp[n]) 이런 기술도 익혀두면 좋을것 같다.

---

코드

#https://www.acmicpc.net/problem/2253
#점프
#2253

import sys
input = sys.stdin.readline

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

n_list = []
for _ in range(m):
    a = int(input())
    n_list.append(a)

# n_list.sort()
# print(n_list)

max_speed = int((2 * n) ** 0.5) + 1

dp = [[float('inf')] * (max_speed+1) for _ in range(n+1)]
dp[1][0] = 0

def fun():

    for i in range(1, n+1):
        stone = i

        if stone in n_list:
            continue

        for j in range(1, max_speed):
            v = j
            dp[stone][v] = min(dp[stone - v][v-1], dp[stone - v][v], dp[stone - v][v+1]) + 1

    return dp

result = fun()
# print(result)
min_jumps = min(dp[n])
if min_jumps == float('inf'):
    print(-1)
else:
    print(min_jumps)