problem-11729

1. an = n번째까지의 원판을 옮길 때, 필요한 횟수
2. a n+1 = n번째까지의 원판을 다른 봉에 옮기기 + n+1번째 원판을 목표 봉에 옮기기 + n번째까지의 원판을 목표봉으로 옮기기
3. a n+1 = an + 1 + an

def hanoi(num,start,middle,dest):
    global cnt
    cnt+=1
    if num==1:
        ans.append((start,dest))
        return
    hanoi(num-1,start,dest,middle)
    hanoi(num-1,middle,start,dest)
    ans.append((start,dest))
n=int(input())
ans=[]
global cnt
cnt=0
hanoi(n,1,2,3)
print(cnt)
for x,y in ans: print(x,y)

time: 50분