하노이탑 푸는 법 — 최소 이동이 2ⁿ−1인 이유

하노이탑은 기둥 세 개 사이로 원반을 한 장씩 옮겨, 첫 기둥의 원반 전부를 마지막 기둥으로 넘기는 퍼즐입니다. 코인 차감이 없고 연령 제한 없이 즐길 수 있습니다.

규칙은 두 줄뿐입니다

• 한 번에 한 장만 옮깁니다. 옮길 수 있는 것은 기둥의 맨 위 원반뿐입니다.
• 큰 원반을 작은 원반 위에 놓을 수 없습니다.

최소 이동이 2ⁿ−1인 이유

맨 아래 원반을 옮기려면 그 위에 있는 n−1장을 통째로 다른 기둥에 비켜 두어야 합니다. 그다음 아래 원반을 한 번 옮기고, 비켜 둔 n−1장을 다시 그 위에 얹습니다.

n−1장을 통째로 옮기는 일이 두 번 필요하므로 T(n) = 2 × T(n−1) + 1이 됩니다. 한 장이면 한 번이니 T(1) = 1이고, 이 식을 풀면 2ⁿ−1이 나옵니다. 3장 7번, 4장 15번, 5장 31번, 6장 63번입니다.

원반이 한 장 늘 때마다 이동이 두 배가 조금 넘게 늘어납니다. 6장이 63번이니 10장이면 1,023번입니다.

외우지 않고 최적으로 두는 법

규칙 하나만 지키면 저절로 최소 이동이 됩니다. 가장 작은 원반을 한 번 걸러 한 번씩 옮기되 언제나 같은 방향으로 돌리고, 작은 원반을 옮기지 않는 차례에는 둘 수 있는 수가 하나뿐이니 그것을 둡니다.

도는 방향은 원반 수가 홀수면 첫 기둥에서 마지막 기둥 쪽으로, 짝수면 반대쪽으로 돕니다. 이 방법이 왜 최적인지는 위의 재귀와 같은 이야기입니다 — 작은 원반이 규칙적으로 돌면서 큰 원반이 옮겨질 자리를 차례로 비워 주기 때문입니다.

되돌리기

방금 옮긴 것을 곧바로 되돌리면 그 수는 기록에서 빠집니다. 잘못 짚었을 때 처음부터 다시 하게 만들 이유가 없기 때문입니다.

기록

이동 횟수가 기록으로 남고 적을수록 순위가 높습니다. 원반 수별로 순위를 따로 매깁니다. 제출할 때는 옮긴 순서를 보내고, 서버가 처음 배치에서 그대로 다시 옮겨 보아 규칙에 어긋나는 수가 없었는지까지 확인합니다.