백준 11729 하노이 탑 이동순서 python 풀이

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

경우의 수

• 원판이 하나도 없는 경우 > 아무것도 안하고 끝
• 원판이 1개밖에 없는 경우 > 3번 기둥으로 옮기고 끝
• 원판이 2개인 경우 > 1번을 2번으로 옮기고, 2번은 3번으로 옮기고, 1을 2에서 다시 3으로 옮긴다.
• 원판이 3개인 경우 > 1&2번을 2번기둥으로 옮기고, 3번을 3번기둥으로 옮김. 그 후 다시 2번기둥에 있는 1&2번을 3번으로 옮김
• 원판이 4개인 경우 > 1&2&3번을 2로 옮겨두고, 4번을 4번기둥으로 옮김 : 재귀적임!

1. 가장 큰 원판을 제외한 나머지 원판을 2번기둥으로 옮긴다.
2. 가장 큰 원판을 3번 기둥으로 옮긴다.
3. 나머지 원판들을 3번기둥으로 옮긴다.

def hanoi(num, start, end):
    if num == 1:
        print(start, end)
        return
    else:
        hanoi(num-1, start, 6-start-end)
        print(start, end)
        hanoi(num-1, 6-start-end, end)

N = int(input())

print(2**N -1)
hanoi(N, 1, 3)