# 하노이의 탑 옮기기
# 원반이 n개인 하노이의 탑을 옮기기 위한 원반 이동 순서 출력
# - 하노이의 탑에는 크기가 다른 원반이 n개 있고
# - 원반을 끼울 수 있는 기둥이 세 개 있다.
# - 원반 n개를 모두 가장 왼쪽 기둥(출발점, 즉 1번 기둥)에서
# - 오른쪽 기둥(도착점, 3번 기중)으로 옮길 수 있을까
# - 제약 조건
#  - 원반은 한 번에 한 개씩만 옮길 수 있다.
#  - 각 기둥 맨 위의 원반을 다른 기둥의 맨 위로만 움직여야 한다.
#  - 옮기는 과정에서 큰 원반을 작은 원반 위에 올려서는 안 된다.
# - 중단에 여분으로 2번 기둥을 잘 활용해야 한다
# [ 규칙 정리 ]
# - 크기가 다른 원반 n개를 출발점 기둥에서 도착점 기둥으로 전부 옮기기
# - 원반은 한 번에 한 개씩만 옮길 수 있다.
# - 원반을 옮길 때는 한 기둥의 맨 위 원반을 뽐아
# - 다른 기둥의 맨 위로만 옮길 수 있다.
# - 기둥의 중간에서 원반을 빼내거나 빼낸 원반을 다른 기둥의
# - 중간으로 끼워 넣을 수 없다
# - 원반을 옮기는 과정에서 큰 원반을 작은 원반 위로 올릴 수 없다.

# 500,100,50,10 
# 아무리 복합한 문제라도 입력 크기가 작은 간단한 문제부터 차근차근 생각

# [ 원반이 한 개일 때 ] - 한번
# 1번 기둥에 있는 원반을 3번 기둥으로 옮기면 끝난다

# [ 원반이 두 개일 때 ] - 세번
# 1번 기둥의 맨 위에 있는 원반을 2번 기둥으로 옮긴다.
# 1번 기둥에 남아 있는 큰 원반을 3번 기둥으로 옮긴다
# 2번 기둥에 남아 있는 원반을 3번 기둥으로 옮긴다.
# 1->2, 1->3, 2->3

# [ 원반이 세 개일 때 ] - 3 + 1 + 3 =7
# 특정 기둥에 있는 원반 두개를 우리가 원하는 기둥으로 옮기는 방법을 알고있다.
# 1번 기둥에 있는 원반 세 개 중에 있는 원반 두개를 2번 기둥으로 옮긴다.
# 규칙에 따라 한번에 원반을 두 개씩 옮길 수 없다
# 두 개일 때 옮기는 방법을 알고 있다.
# 3번 기둥을 보조 기둥으로 사용하여 1번 기둥에 있는 원반 두 개를 
# 2번 기둥 기둥으로 옮기낟 1->3, 1->2, 3->2
# 1번 기둥에 남아있는 큰 원반을 3번 기둥으로 옮긴다.
# 2번 기둥에 원반 3개를 3번 기둥으로 옮긴다.
# 1번 기둥을 보조 기둥으로 활용하여 2번 기둥에 있는 원반 두개를 3번으로 옮김
# 2->1, 2->3, 1->3 
# 1->3, 1->2, 3->2, 1-3, 2->1, 2->3, 1->3

# [ 원반이 n개일 때 ]
# 1번 기둥에는 n-1개 원반을 2번 기둥으로 옮긴다
# 1번 기둥에 남아있는 가장 큰 원반을 3번 기둥으로 옮긴다.(1->3)
# 2번 기둥에 있는 n-1개 원반을 3번 기둥으로 옮긴다.

# 원반이 한 개면 그냥 옮기면 끝난다.
# 원반이 n개 일때 
#  1번 기둥에 있는 n개 원반 n-1개를 2번 기둥으로 옮긴다
#  ( 3번 기둥을 보조 기둥으로 사용)
#  1번 기둥에 남아있는 가장 큰 원반을 3번 기둥으로 옮긴다.
#  2번 기둥에 있는 n-1개 원반을 다시 3번 기둥으로 옮긴다.
#  ( 1번 기둥을 보조 기둥으로 사용)
# 원반이 한 개일 때가 바로 '종료 조건'에 해당도니다.
# 원반 n개 문제를 풀려면 n-1개 원반 문제를 풀어야 한다.
# 이는 바로 '좀 더 작은 값으로 자기 자신을 호출'하는 재귀 호출이다.
 