[백준/파이썬Python] #2253 점프 : 퐁당퐁당 인덱스 머리쓰기 🪨

🪨 문제

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

• N(순서대로 1, 2, …, N번 돌)개의 돌
  현재 1번 돌 위, 점프 하면서 N번째 돌로 이동을 하려 함

1. 이동은 돌 번호가 증가하는 순서대로만 할 수 있음
2. 제일 처음에 점프를 할 때에는 한 칸밖에 점프하지 못함.
   이전에 x칸 점프를 했다면, 다음번에는 x-1칸 점프하거나, x칸 점프하거나, x+1칸 점프를 할 수 있음. 물론 점프를 할 때에는 한 칸 이상씩 해야 함.
3. 몇 개의 돌은 크기가 너무 작기 때문에 올라갈 수 없음.

• 위와 같은 조건들을 만족하면서 1번 돌에서 N번 돌까지 점프를 해 갈 때, 필요한 최소의 점프 횟수 구하기

🧠 접근 방법

이 문제는 위의 점화식을 사용하기 위해서 DP 테이블을 만드려면 인덱스가 헷갈립니다. 행 번호의 경우는 0~N(돌 번호)이므로 N+1인데 열 번호의 경우도 N+1이 가능하지만 최적의 범위는 아닙니다. 열 번호 즉, 점프의 최댓값을 구하기 위해서는 등차수열의 합 공식을 이용하면 됩니다.

입력

• 첫째 줄: N(돌 번호), M(크기가 작은 돌의 개수)
• ~(M개): 크기가 작은 돌들의 번호

출력

• 필요한 최소의 점프 횟수

• 만약 N번 돌까지 점프해갈 수 없는 경우, -1 출력

👩🏻‍💻 코드

DP = [[float("inf") for _ in range(int(((2*N)**0.5)+2))] 

이 부분이 가장 헷갈렸는데 일단 이 부분을 이해하기 위해서는 아래 for문을 먼저 보고 오면 이해하기가 더 쉽습니다.
아래 for문을 이해하셨다고 생각하고, 그럼 int(((2*N)**0.5)까지 보고 싶으면 1을 더해줘야 하는데 1을 더 더해준 이유는 for문 안의 마지막 값인 DP[i-j][j+1]에서 j+1값을 찾기 때문입니다. 만약 int(((2*N)**0.5)+1으로 하면 j+1값은 없기 때문에 인덱스에러가 발생하게 됩니다.

DP[1][0] = 0

시작돌에서 시작돌로 가는 초기값만 0으로 초기화해줍니다.

for i in range(2, N+1):

0돌은 존재하지 않고, 1돌은 시작돌이기 때문에 1돌로 오는 횟수는 없기 때문에 2부터 시작합니다.

    if i in rocks:
        continue

작은 돌은 올라갈 수 없기 때문에 넘어갑니다.

    for j in range(1, int(((2*N)**0.5)+1)):

점프의 최댓값은 int(((2*N)**0.5)인데 range에서 해당 값까지 보기 위해서는 1을 더해줘야 합니다.

📑 전체 코드

# 점프 - DP
import sys
N, M = map(int, sys.stdin.readline().split())
rocks = []
for _ in range(M):
    rocks.append(int(sys.stdin.readline()))

DP = [[float("inf") for _ in range(int(((2*N)**0.5)+2))] for _ in range(N+1)]
DP[1][0] = 0

for i in range(2, N+1):
    if i in rocks:
        continue
    for j in range(1, int(((2*N)**0.5)+1)):
        DP[i][j] = min(DP[i-j][j], DP[i-j][j-1], DP[i-j][j+1]) + 1 

if min(DP[-1]) == float("inf"):
    print(-1)
else:
    print(min(DP[-1]))