[Python]재귀 백준 11729

문제

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

친숙한 문제이다. 몇몇분들은 실제로 해봤을것이다.

재귀와도 잘 맞는 문제이다. 하지만 실제로 방법을 아는것과 구현하는 것은 조금 다를수

 있다는걸 깨달았다.

def hanoi(n,start,mid,end):
    if n==1:
        print(start, end)
 
    else:               #다음 원판을 옮기기 위해선
        hanoi(n-1,start,end,mid)    #이전완성단계 에서
        print(start, end)           #제일아래에 들어갈 원판을 옮기고
        hanoi(n-1,mid,start,end)    #이전 단계에서 했던방식을  통해 제일 아래에 들어갈 원판 위에 다시쌓는다.
        
        
n=int(input())
sum=1
for i in range(n-1):    #총옮길 횟수는 따로 계산해줬다.
    sum=sum*2+1     #두번째 else문에서 보이듯이 이전단계보다 2배+1만큼 늘어나는 걸 볼수있다.
print(sum)  #총횟수 출력
hanoi(n,1,2,3)