bj11729 하노이 탑 이동순서

음.. 우선 n= 1인 base case는 무조건 source에서 destination으로 옮겨야한다.

n >= 2이라면 n-1개의 원판을 extra 막대기로 옮기고
1개의 원판을 destination으로 옮기고
다시 그 n-1개의 원판을 destination에 옮기면 된다.
따라서 recursive의 알고리즘이 적용된다!

따라서 이를 source code로 작성하면

def hanoi(disks, src, dst, extra):
    if disks == 1:
        hanoi.count += 1
        print(f'{src} {dst}')
    else:
        hanoi(disks - 1, src, extra, dst)
        hanoi.count += 1
        print(f'{src} {dst}')
        hanoi(disks - 1, extra, dst, src)


hanoi.count = 0
n = int(input())
print(2**n - 1)
hanoi(n, 1, 3, 2)

다음과 같다.
아 hanoi.count는 static variable처럼 동작하는 아이인데
백준에서 요구하는 출력이 몇 번 이동시키는지를 나타내라고 해서 넣었던 아이인데 사실 처음에 생각했던 것은 총 이동 횟수를 이 변수에 저장하고
append함수로 src와 dst를 저장한 후 마지막에 출력시키려고 했다.
근데 big O 계산하면서 이동횟수를 2's n squared - 1인 것을 알게 되어서 이걸로 하고 hanoi.count를 지우는 것을 깜빡함.