[백준/2253] 점프 (Python)

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

 

Difficulty : Gold 4

 

Status : Solved

 

Time : 00:31:31

 

---

 

문제 설명

 

 

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을 출력한다.

 

입력 예시

 

19 3
11
6
16

 

출력 예시

 

6

 

 

---

 

풀이

 

DP 문제. i번째 시점에서 직전의 점프 거리가 j일 때, 최단 점프의 경우의 수를 DP[i][j]라 두자. 그렇다면 k ∈ {j-1, j, j+1}에 대하여, DP[i+k][k]를 DP[i][j] + 1 값으로 업데이트할 수 있게 된다. 몇몇 예외처리 (다음 점프 거리가 1 ~ N사이인지 확인, 첫 번째 점프는 1칸만 가능, 크기가 너무 작은 돌 예외처리) 만 해 주면 완벽하게 풀이할 수 있다.

 

또한, 본 문제는 메모리가 짜다. 따라서 DP를 2차원 배열로 선언하되, 최적화된 구조로 선안하지 않으면 메모리 초과를 보기 십상이다.

 

1번부터 N번까지, 총 N-1개의 칸을 점프한다고 가정하자. 이 때 가장 최소로 주파하는 경우, 또한 N 시점에서 최대 점프 거리 x를 얻는 경우는 가속 점프만을 시행했을 때, 즉 ∑x 꼴로 점프 거리가 나오게 된다. 즉 다음이 성립한다.

 

 x(x+1) / 2 ≦ N-1

 

이를 러프하게 풀어보자. x, N은 자연수이므로,

 

 x(x+1) / 2 < N

x^2 < x(x+1) < 2*N

x < root(2*N)

 

꼴이 된다. 즉 최대 점프 횟수를 root(2*N)으로 잡고 풀이하면 훨씬 메모리적으로 효율적이게 배열을 선언할 수 있다.

 

풀이 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
MAX = int((2*N)**0.5)+1
small_rocks = [False]*N
for _ in range(M) :
  small_rocks[int(input()) - 1] = True

dp = [[N]*MAX for _ in range(N)]
if not small_rocks[1] :
  dp[1][0] = 1 
for i in range(1, N-1) :
  if small_rocks[i] :
    continue
  for j in range(MAX) :
    if dp[i][j] == N :
      continue
    for k in [j-1, j, j+1] :
      if -1 < k < MAX and i+k+1 < N and not small_rocks[i+k+1]:
        dp[i+k+1][k] = min(dp[i+k+1][k], dp[i][j] + 1)

answer = min(dp[-1])
print(answer if answer < N else -1)

풀이 완료!