[백준] 11729 하노이탑 이동 순서 파이썬 풀이 (재귀)

코드

def hanoi(disk, start, mid, end):
    if disk == 1:
        print(start, end)
    else:
        hanoi(disk - 1, start, end, mid)
        print(start, end)
        hanoi(disk - 1, mid, start, end)

total_disk = int(input())
total_mvmt = 0

for disk in range(total_disk):
    total_mvmt = total_mvmt * 2
    total_mvmt += 1

print(total_mvmt)
hanoi(total_disk, 1, 2, 3)

풀이

 

하노이탑 옮기기의 원리이다

5개의 탑을 3번으로 옮기려면

일단 4개를 중간으로 옮겨놓고

5번을 3번으로 옮긴다음

중간에 있던 4개를 3번으로 옮기면 된다.

 

그럼 4개를 옮기는 법은 똑같이

3개를 다른데 옮겨놓고 4번을 3번에 옮겨놓고 3개를 그 위에 얹으면 된다

 

그렇게 계속 하나씩 줄여가면서 옮기면 된다.

 

그리고 총 몇 번 움직였는지는 이 공식으로 출력하면 된다.

3개 원반을 1번에서 3번으로 옮기려면 2개 원반을 2번 막대로 옮기고 ,

3번 원반을 3번 막대에 옮기고 , 2개 원반을 3번막대에 옮겨야한다.

2개의 원반을 2번 옮겨야하고 3번 원반을 1번 옮긴다.

그래서 저 공식이 나왔다.