숨바꼭질 3

• 간단한 방법은 그냥 조건대로 각 위치를 노드로 만들고, 노드마다 3개씩의 엣지를 만들어서 단일 출발지 최단 경로 (Single Source Shortest Path) 알고리즘으로 푸는 것이다. 코스트가 0 또는 1만 존재하므로 0-1 BFS를 사용해서 풀 수 있다.
• 하지만, 조금 더 조건을 분석하면 최적화할 여지가 많이 있다.
  • N이 K보다 커지면 *2나 +1로 이동하는것은 최단 경로가 될수 없다. 거기에서는 무조건 N-K번 -1을 해주는것이 최적이다
  • 최단경로에 *2 로 이동하는것이 한번이라도 포함된다면, K/2에서 K로 이동하는 것은 무조건 최단 경로에 포함되어야 한다. (K가 홀수일때는 (K-1)/2에서 K-1로 이동하거나, (K+1)/2에서 K+1로 이동하거나..). 이유는 현재의 위치가 어디든간에, K/2로 이동한 뒤에 K로 이동하는 비용인 abs(N-K/2)가 다른 곳 x로 이동한 뒤에 x*2로 이동한 뒤에 거기에서 K로 이동하는 비용인 abs(N-x) + abs(K-x*2) 보다 작다.
• 이 조건들을 적용하면, 그냥 점화식을 세워서 DP로 계산하는 것도 가능하다. dp[k]를 구하기 위해서는 k가 홀수일때는 dp[(k-1)/2]와 dp[(k+1)/2], k가 짝수일때는 dp[k/2]만 필요하므로, top-down 으로 풀면 O(logK)개의 노드만 갖고 계산할수도 있다.
• 그리고 top-down dp를 재귀로 구현하기가 싫으면, 그냥 K와 (K-1)을 각각 2로 나눠가면서 이터레이티브하게 계산하는것도 가능하다. 실제로는 이렇게 구현했다. 시간복잡도는 역시 O(logK)

"""Solution code for "BOJ 13549. 숨바꼭질 3".

- Problem link: https://www.acmicpc.net/problem/13549
- Solution link: http://www.teferi.net/ps/problems/boj/13549
"""


def main():
    N, K = [int(x) for x in input().split()]

    k1, d1, k2, d2 = K, 0, K - 1, 1
    answer = abs(K - N)
    while k2 > 0:
        if k1 % 2 == 1:
            k1, d1, k2, d2 = k1 // 2 + 1, d1 + 1, k2 // 2, min(d1 + 1, d2)
        else:
            k1, d1, k2, d2 = k1 // 2, min(d1, d2 + 1), k2 // 2, d2 + 1
        answer = min(answer, d1 + abs(N - k1), d2 + abs(N - k2))
    print(answer)


if __name__ == '__main__':
    main()