1914 하노이 탑

하노이 탑에 원판이 n개 쌓여있을때, 옮기는데 드는 총 횟수와 옮기는 과정을 출력하는 문제이다.

하노이 탑이란
3개의 기둥이 있고, 처음 기둥에 n개의 원판이 크기가 큰 순서대로 쌓여있다.
이 원판들을 3번째 원판에 모두 옮겨야 하는데,
한번에 1개의 원판만 옮길 수 있고, 작은 원판위에 큰 원판을 올릴 수 없다는것이 규칙이다.

스페셜 저지 문제가 아니기 때문에 항상 최적의 경우를 구해야만 하는데,
최적의 해의 횟수는 2^n - 1 번이다.
머리를 짜보았지만 도저히 알고리즘이 떠오르질 않아서 검색을 했는데,
재귀를 이용해서 문제를 푸는 것이었다.

답은 맞았지만 알고리즘을 봐도 원리가 정확히 이해가 되지 않아서 푼거같지가 않다..

소스