사용자 도구

사이트 도구


ps:problems:boj:13549

숨바꼭질 3

ps
링크acmicpc.net/…
출처BOJ
문제 번호13549
문제명숨바꼭질 3
레벨골드 5
분류

DP

시간복잡도O(logn)
인풋사이즈n<=100,000
사용한 언어Python
제출기록30840KB / 68ms
최고기록64ms
해결날짜2022/09/22

풀이

  • 간단한 방법은 그냥 조건대로 각 위치를 노드로 만들고, 노드마다 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()

토론

댓글을 입력하세요:
X V X A Z
 
ps/problems/boj/13549.txt · 마지막으로 수정됨: 2022/09/22 16:50 저자 teferi