문제출처 : https://www.acmicpc.net/submit/11729/33677793

풀이과정

1. n-1 개의 원판을 6-start-end 막대로 옮긴다.

2. 마지막 n번 원판을 end 막대로 옮긴다.

3. n-1개의 원판을 6-start-end 막대에서 end 막대로 옮긴다.

4. 내가 만들어야 할 함수는 start -> end로 원판을 옮기는 함수이다.

5. 가장 중요한 점은 6-start-end 를 생각해내는 것이다....

answer =[]
def solve(n,start,end):
    global answer
    if n == 1:
        answer.append((start, end))
    else:
        solve(n-1,start,6-start-end) # 1단계 n-1 개의 원판을 2번 막대로 옮김
        answer.append((start,end)) # 2단계 마지막인 n번 원판을 3번 막대로 옮김
        solve(n-1,6-start-end,end) # 3단계 : 2번 원판의 n-1개의 원판을 3번 막대로 옮김

solve(int(input()),1,3)

print(len(answer))
for i in answer:
    print(i[0],i[1])