Baekjoon 23250. 하노이 탑 K / Python

23250. 하노이 탑 K

난이도 : 골드 4
소요 시간 : 30분
날짜 : 2025.01.02
언어 : 파이썬
알고리즘 유형 : 재귀, 이분탐색

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. n개의 원판이 있는 하노이탑에서 k 번째 이동을 구하시오

2. 해결 방식

1. 이분탐색 + 재귀
2. 일반적인 하노이 탑의 재귀함수를 사용한다.
3. 바뀌는 점
   • 전체경로를 구하는게 아니므로, 하노이탑 전체 크기를 계속 하나씩 줄여나갈 수 있다.
   • 만약 중앙을 옮기는 경우라면 바로 출력하면 되고,
   • 중앙 이후의 경우라면, k값을 갱신해주면서 재귀함수를 돌리면 된다.

3. 정답 코드

n, k = map(int, input().split())

def hanoi(x:int=n, now:int=k, a:int=1, b:int=3, c:int=2):
    if x == 1:
        if now == 1:
            print(a, b)
        return

    half = 2**(x - 1)
    if now < half:
        hanoi(x - 1, now, a, c, b)
    elif now == half:
        print(a, b)
    else:
        hanoi(x - 1, now - half, c, b, a)

hanoi()