백준 1697 숨바꼭질

문제

숨바꼭질

숨바꼭질 놀이에서 동생을 찾는 최소 시간을 구하자

난이도 : Silver1

---

풀이

1. dp로 순간이동과 걷는 케이스를 모두 비교해 최솟값을 dp list에 저장

---

코드

import sys

N, K = tuple(map(int, sys.stdin.readline().split()))

def find(n, k):
    if k <= n:
        return n-k

    dp = [0] * 100001
    for i in range(1, 100001):
        if i <= n:  # 동생이 더 가까이 있으면
            dp[i] = n - i  # 뒤로는 순간이동을 못하므로 단순 뺄셈
            
        else:
            dp[i] = dp[i-1] + 1  # 이전 위치에서 1 이동
            if i % 2 == 0:  # 순간이동이 가능한 경우
                dp[i] = min(dp[i//2] + 1, dp[i])  # 2로 나눈 위치 + 1, 이전 위치 + 1 중 최솟값
    
    
        dp[i-1] = min(dp[i-1], dp[i]+1)  # 다음 위치에서 1을 더하는 것과 비교하는 것은 한 스텝 느리게 진행해야 제대로 갱신 가능
        
    return dp[K]

print(find(N, K))

---

결과

확실히 다이나믹 프로그래밍에 너무 약해 어렵게 푼 것 같다.