[백준] 11729 하노이 탑

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

11729번: 하노이 탑 이동 순서

N = int(input())


def hanoi(N, x, y):
    if N == 1:
        print(x, y)
    else:
        hanoi(N-1, x, 6-x-y)
        print(x, y)
        hanoi(N-1, 6-x-y, y)

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

솔직히 하노이탑의 규칙을 모르겠어서 구글링을 좀 해봤다..

 

우선 N개의 고리가 1번 장대에 있을 때 N-1개를 2번 장대로 옮겨두고 3번장대에 마지막 고리를 둔 후 2번 장대에 옮겨둔 것들 중 N-2개를 1번 장대에 옮겨두고 다시 마지막 장대를 3번장대로 옮겨두고를 반복하면 된다.

 

예를들어 3개의 원반을 1에서 3으로 보내려면

 

1, 3의 좌표에서 2번으로 다 옮겨놔야 하므로 6에서 1, 3을 뺀 2로 옮기고 나머지 하나를 3으로 옮긴 후 다시 2번의 원반을 3번으로 옮기면 해결이다.

 

이걸 코드로 짜는것도 너무 어려워 도움을 좀 받았다 ㅎㅎ 재귀는 너무나 어려운 것 같다.