백준 11729 : 하노이 탑 이동 순서 (파이썬)

하노이 탑 이동 순서

 

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

 

 

---

코드

def hanoi(n):
    if n == 1: return ["1 3"]
    #짝수일때는 오른쪽으로 한칸씩
    if n % 2 == 0:
        tmp = ["1 2", "2 3", "3 1"]
    #홀수일때는 왼쪽으로 한칸씩
    else:
        tmp = ["1 3", "3 2", "2 1"]
    pre = hanoi(n - 1)
    new = []
    for i in range(len(pre)):
        new.append(tmp[i % 3])
        new.append(pre[i])
    else:
        new.append(tmp[len(pre) % 3])
    return new
hanoiList = hanoi(int((input())))
print(len(hanoiList))
print('\n'.join(hanoiList))

해설

문제를 보자마자 규칙이 떠오르지 않아 n을 늘려가면서 하나씩 적어보았다.

이렇게 하나씩 나열해보니 규칙이 보이기 시작했다.

hanoi(1) = 1 3

hanoi(2) = 1 2, hanoi(1) 첫 번째 동작, 2 3

hanoi(3) = 1 3, hanoi(2) 첫번째 동작, 3 2, hanoi(2) 두 번째 동작, 2 1, hanoi(2) 세 번째 동작, 1 3

hanoi(4) = 1 2, hanoi(3) 첫번째 동작, 2 3, hanoi(3) 두 번째 동작, 3 1, hanoi(3) 세 번째 동작,... , 1 2, hanoi(3)의 마지막 

hanoi(n) =
n이 짝수라면 원판을 한칸씩  오른쪽으로 이동하는 사이에 hanoi(n-1) 동작이 추가된다. (3번째 장대일 땐 1번째 장대로)

n이 홀수라면 원판을 한칸씩  왼쪽으로 이동하는 사이에 hanoi(n-1) 동작이 추가된다. (1번째 장대일 땐 3번째 장대로)

 

즉, hanoi(n)을 호출 시 

hanoi(n) -> hanoi(n-1) -> ... -> hanoi(1)까지 거슬러 올라가 hanoi(1)부터 차근차근 만들어 반환하게 된다.