[python] 점프 백준 2253

Designated Hitter Jack·2023년 8월 30일

백준 - 파이썬

목록 보기

7/26

문제

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

예제 입력 1

예제 출력 1

나의 풀이

#dp에 저장해야 할 값 = 각 칸에 도착하기 위해 필요한 최소한의 점프 횟수
#그러나 각 돌에 어떤 속도로 도달하냐에 따라서 다음 돌에 도착하는 횟수 역시 달라지며, 그 속도 때문에 마지막 돌에 못 가는 경우 역시 생기므로
#dp는 각 돌에 도착하기 위한 최소한의 점프 횟수 + 그 돌에 도착했을 때의 속도 역시 기록하는 2차원 리스트가 되어야 함

import sys
input = sys.stdin.readline

N, M = map(int, input().split()) #N: 돌의 개수, M: 크기가 작아서 밟을 수 없는 돌의 개수
small_stones = []
for _ in range(M):
    small_stone = int(input())
    small_stones.append(small_stone)

dp = [[float('inf')] * (int((2*N)**0.5) + 2) for _ in range(N + 1)]
#(2*N) ** 0.5) + 1은 첫째항이 1이고 공차가 1인 등차수열에서 수열의 합이 N이 될 때 마지막 항의 근사값, 즉 돌의 갯수가 N개일 때 나올 수 있는 속도의 최대값에 가까운 값
#최대 속도의 정확한 값이 필요한 것이 아니라 이 이상 넘어설 수 없는 최대값을 (계산하기 더 편하게 정수로) 대충이나마 설정하는 것이 더 중요하기 때문에 정확한 값보다 더 큰 근사값을 설정

dp[1][0] = 0

for i in range(2, N + 1):
    if i in small_stones:
        continue
    for j in range(1, int((2*i)**0.5) + 1):
        dp[i][j] = min(dp[i-j][j-1], dp[i-j][j], dp[i-j][j+1]) + 1
#점화식: i라는 점에 j라는 속도로 도달했을 때 최소 점프 횟수는 i-j의 위치에 따라 (각각 j-1, j, j+1의 속도로 도달했을 때 시행한 점프) + 1
if min(dp[N]) == float('inf'): #목표지점까지 갈 수 없음
    print(-1)
else:
	#dp[N]은 각각의 속도로 N에 도착했을 때 얻을 수 있는 점프의 여러 값들이 배열로 구성되어 있는데, 그 중 최소값을 출력
    print(min(dp[N]))