[백준 11729번] 하노이의 탑

문제 링크: 11729번 하노이 탑 이동 순서

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

 

from, mid, to가 있을 때,

n개를 from에서 to로 옮기기 위해서는...

 

1. n-1개를 from에서 mid로 옮긴다.

2. 1개를 from에서 to로 옮긴다.

3. n-1개를 mid에서 to로 옮긴다.

 

이런 아이디어를 기본으로 생각하면 되는 것 같다.

 

def hanoi(n, f, m, t, arr):
    if n==1:
        arr[0] += 1
        arr.append("{f} {t}".format(f=f, t=t))
        return

    hanoi(n-1, f, t, m, arr)
    hanoi(1, f, m, t, arr)
    hanoi(n-1, m, f, t, arr)
    return

n = int(input())
arr = [0]
hanoi(n, 1, 2, 3, arr)

for i in range(len(arr)):
    print(arr[i])