점프 (백준 2253번 - 파이썬)

풀이

필요 요소
1. 못 건너는 돌 위치를 저장할 리스트
2. 현재 돌까지 점프해서 올 수 있는 이전 돌의 점프 횟수를 기록할 2차원 dp배열

dp배열에 대해 설명을 추가하자면
dp[i][v]라 하면 i번째 돌(y축)로 v의 속도(x축)로 왔을 때의 최소값이라 할 수 있다.
dp[i][v]로 올 수 있는 경우는 dp[i-v][v-1], dp[i-v][v], dp[i-v][v] 이렇게 있는 셈이다.

dp값들을 max로 초기화해주고	dp[1][0]을 0으로 초기화 시키고

올 수 있는 돌들 중에서 최소값에 1을 더해	현재 돌의 점프 최소값을 갱신해준다

int((2*N)^0.5)의 의미
-> 불필요한 연산을 막기 위한 연산
등차수열의 합 공식 = k(2a+(k-1)d) / 2
(이 문제에서 a(첫 번째 수) =1, d(공차) =1 )
따라서 마지막에 있는 돌까지 가장 빠르게 갈 수 있는 돌들의 수의 합 N
= k(k+1)/2
k = (2N-k)^0.5 <= 2N^0.5

코드

from sys import stdin

N, stone_n = map(int, stdin.readline().split())

stone = set()
for _ in range(stone_n):
    stone.add(int(stdin.readline().rstrip()))

dp  = [[10001]* (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 stone:
        continue
    for v in range(1,int((2*i)**0.5)+1):
        dp[i][v] = min(dp[i-v][v-1],dp[i-v][v],dp[i-v][v+1]) +1


ans = min(dp[N])
if ans == 10001:
    print(-1)
else:
    print(ans)

후기

갈피를 못 잡아서 다른 사람들 코드를 봤는데 봐도 이해하는 데 꽤 오래 걸렸다.
int((2*N)**0.5) 이 부분도 등차수열의 합까지 검색해서야 알게 됐다.
고딩 때 배운 거 같은데 기억이 안나...흑흑
문돌이 출신 개발자들 모두 힘내쟈ㅑㅑㅑㅑㅑㅑㅑㅑㅑㅑ