하노이 탑 이동 순서

문제

백준 11729번
https://www.acmicpc.net/problem/11729

풀이

• 작은 숫자부터 생각해본다.
• 하나일 경우는 1 -> 3으로 옮기면된다.
• 2개일 경우는 맨 위를 중간으로 옮기고 마지막 링을 3번으로 옮기고 중간에 있는 링을 3번으로 옮기면 끝난다.
• 그럼 n개인 경우는?
• 2개일 경우와 똑같다.
• n-1개를 가운데로 옮기고 마지막 n번째 링을 3번으로 옮긴 후 다시 n-1개를 3번으로 옮기면 된다.

코드

import sys

input = sys.stdin.readline

n = int(input())

def hanoi(num, now, to):
    if num == 1:
        print(now, to)
    else:
        hanoi(num-1, now, 6-now-to)
        print(now, to)
        hanoi(num-1, 6-now-to, to)


if __name__ == "__main__":
    print(2**n-1)
    hanoi(n, 1, 3)

• 특정 개수를 1에서 3으로 옮겨야 한다.
• 1과 3일 경우 2로 옮기는게 명확하지만 중간 과정에서는 시작 위치와 끝 위치만 알기 때문에 어디로 옮겨야할지 잘 모를 수 있다.
• 그래서 6-now-to로 이동할 곳을 찾는다.