백준 점프 2253 : 쉽게 나온 풀이

백준의 dp문제 점프를 풀었다.

사고의 흐름

기본적으로 배낭문제랑 비슷하게 속도와 거리로 이차원 배열을 만들면 풀 수 있겠다는 생각을 했다.

기본적으로 dp를 dp[i][v]로 구성하여 그 의미를 i번째 돌에 v의 속도로 들어왔을 경우의 최소값이라고 생각을 해보자.

그렇다면 i번째 돌에 v의 속도로 들어올 수 있는 경우는 어떤 경우가 있을까?

i번째 돌에 v의 속도로 들어오기 위해서는 i-v번째 돌에서 v의 속도로 뛰는 경우밖에 없다.
그러나i-v번째 돌에서 v의 속도로 뛸 수 있는 경우는 세가지가 있다.

1. dp[i-v][v-1] 에서 가속을 하면서 뛸 경우
2. dp[i-v][v] 에서 속도 유지를 하면서 뛸 경우
3. dp[i-v][v+1]에서 감속을 하면서 뛸 경우

이 세가지의 경우는 모두 dp[i][v]로 도달할 수 있는 값이 되고, 거기에 한번 뛰었다는 의미로 1을 더해주면 dp[i][v]가 되는 것이다. 우리는 최소 점프 횟수를 구하고 싶기때문에 이 세가지 경우 중 최소값으로 저장을 해주면 되는 것이다.

이렇게 생각을 해보면 점화식이 간단하게 세워진다. dp[i][v] = min(dp[i-v][v-1], dp[i-v][v], dp[i-v][v+1])+1

여기에 작은 돌에 닿았을 때는 갈 수 없다는 표시를 해주면 되는 것이다.

조금 더 생각해볼 부분은 i에 따라서 최대의 v가 결정될 수 있다는 점으로, 쓸데없이 큰 v값까지 검사하면서 시간을 낭비할 가능성을 최대한으로 제거하기 위해서, 약간의 초등수학을 사용해 최적화할 수 있다.

v*(v+1)/2 = i

이 식의 해를 구하면 i의 위치에서 받을 수 있는 최대의 속도가 나오게 된다.

코드

import sys
from math import sqrt
input = sys.stdin.readline


def solve():
    N, M = map(int, input().split())

    dp = [[float('inf')]*(int(1.5*(N**0.5) + 2)) for _ in range(N+1)]
    dp[1][0] = 0
    trap = set()
    for _ in range(M):
        trap.add(int(input()))

    for i in range(2, N+1):
        if i in trap:
            continue
        for v in range(1, int(sqrt(2*i))+1):
            dp[i][v] = min(dp[i-v][v-1], dp[i-v][v], dp[i-v][v+1]) + 1

    result = min(dp[N])
    if result == float('inf'):
        print(-1)
    else:
        print(result)


solve()

사족

글만 써놓고 보면 엄청나게 쉽게 푼 것처럼 느껴진다. 그런데 막상 실제 할 때는 온갖 인덱스 오류(sqrt(2n)이 맞다는 확신이 없었기에 생겼던)와 세부적인 점화식의 문제 때문에 고통스러운 경험을 했었다.

문제를 풀고 있을 때는 언제나 내가 생각한 풀이가 맞는건지 틀린건지, 실수는 없었는지 혼란스럽기 때문에, 코드가 산으로 갈 때도 있고, 아니면 나의 생각이 마구 혼란스러워지면서 다시 생각을 해야하는 순간이 오기도 한다.

그런 일들이 있었음에도 내가 이렇게 글을 쓰고 있다는 것이 조금 웃긴 일이다.

반대로 생각해보면 다소 희망적인 메시지를 찾아볼 수 있다. 남들이 쉽게 써놓은 풀이 해설들도 사실은 긴 고민의 시간 끝에 작성되었을 수도 있다는 사실.

그러니까 왜 난 안될까 고민하느라 시간낭비 하지말고 그냥 공부나 하면 될 듯 싶다. 이렇게 보니 나도 무슨 무림 고수마냥 쉽게 말하고 있지 않은가..