[백준] 11729번 : 하노이 탑 이동 순서(python)

아이디어 1

- 원판들이 있는 장대의 번호(start = 1), 원판들을 옮기고 싶은 장대의 번호(end = 3)을 알고 있음.

- 그럼 남은 장대의 번호는 1+2+3 = 6이기때문에, 6-start-end 로 구할 수 있다!

 

아이디어2

사실 아직까지는 재귀 알고리즘이 한번에 생각나지 않고, 저렇게 작은 숫자를 대입해서 직접 그려봐야 반복되는 것이 보인다.

import sys
input= sys.stdin.readline



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

n=int(input().strip())
k = 2**n-1
print(k)
hanoi(n, 1, 3)