백준11729(파이썬) - 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

• 하노이 탑문제는 아주 유명한 재귀 문제이다.
• 재귀문제를 생각할 때는 function(n-1)이 function(n)한테 영향을 미치는지를 잘 생각해봐야 한다.
• 하노이 탑 같은 경우에는 첫 번째 장대에서 세 번째 장대로 옮기는 문제이고, 경우의 수를 생각해서, 첫 번째에서 두번째를 경유해서 세 번째를 가는 경우와, 그 다음으로 두 번째로 옮긴 장대들을 세 번째로 옮겨주는 경우 두가지를 생각해서 재귀함수를 작성해준다.
• 하노이 탑 이동횟수는 2**n-1 회 이다.

1. 첫 번째 장대에 있는 n-1 개의 원반을 두 번째 장대로 옮긴다.

2. 첫 번째 장대에 남아 있는 원반중 가장 큰 원반을 세 번째 장대로 옯긴다.

3. 두 번째 장대에 있는 n-1개 원반을 세 번째 장대로 옮긴다.

4. n이 가장 큰 원반이라고 생각하면된다.

import sys
input = sys.stdin.readline

n = int(input())

print(2**n-1)
def hanoi(n,start,end,via):
    if n == 1:
        print(start,end)
    else:
        # 1에서 3으로 가기위해서 2로 다 옮겨놓는다.
        hanoi(n-1,start,via,end)
        # 1에서 3으로 간다.
        print(start,end)
        # 2 에 있던걸 모두 3으로 옮긴다.
        hanoi(n-1,via,end,start)
hanoi(n,1,3,2)