BOJ_13913(숨바꼭질4)

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

접근 방식

1. 먼저 0 <= n < 100,000의 범위를 고려했을 때, 투포인터, 이분탐색, 스택, DP 등을 생각해 볼 수 있다.
2. 모든 좌표에서 동일한 방식(이전 좌표 고려, 나누기 2 좌표 고려..)으로 문제를 해결할 수 있다. 고로 DP를 사용하는 것이 적절하다.

구현

알고리즘 요약:
DP를 이용해 N부터 K까지의 거리를 구한다 →
DFS를 이용해 N부터 K까지의 경로를 추적한다 →

import sys, copy
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

# 입력
N, K = map(int, input().split())

# DP 구하기
dp = [-1] * (100_001)
dp[N] = 0

for i in range(N - 1, -1, -1):
    dp[i] = dp[i + 1] + 1

for i in range(N + 1, 100_001):
    dp[i] = dp[i - 1] + 1

    if i % 2 == 0 and dp[i // 2] != -1:
        dp[i] = min(dp[i], dp[i // 2] + 1)

    if (i + 1) % 2 == 0 and dp[(i + 1) // 2] != -1:
        dp[i] = min(dp[i], dp[(i + 1) // 2] + 2)

# DP 리스트를 DFS 탐색
result = []
def dfs(current, path):
    global result

    if result: return

    if current == N:
        result = copy.deepcopy(path)
        return
    
    # -1
    if current + 1 < len(dp) and dp[current] - 1 == dp[current + 1]:
        path.append(current + 1)
        dfs(current + 1, path)
        path.pop()

    # +1
    if current - 1 < len(dp) and dp[current] - 1 == dp[current - 1]:
        path.append(current - 1)
        dfs(current - 1, path)
        path.pop()

    # x2
    if current % 2 == 0 and dp[current] - 1 == dp[current // 2]:
        path.append(current // 2)
        dfs(current // 2, path)
        path.pop()

dfs(K, [K])

# 결과
print(dp[K])
print(' '.join(map(str, result[::-1])))