3+1 하노이 탑

• 다음 방법처럼 처리하면 된다.
  • 1) N개의 원반이 x에 놓여져 있다
  • 2) N-2개의 원반을 x에서 y로 옮긴다. 이때 z를 임시 기둥으로 활용한다. 이것은 일반 하노이 탑과 동일한 방식으로 재귀적으로 처리한다.
  • 3) x에 남아있는 2개의 원반을 'D'로 옮긴다. 이때 z를 임시 기둥으로 활용한다. x→z, x→'D', z→x 의 3단계로 처리된다
  • 4) 이제 다시 N-2개의 원반이 z에 놓여져 있는 상태가 된다. 1단계로 돌아가서 반복한다.
• 총 이동 횟수는 O(2^n)이다. 이동 횟수만큼 이동 과정을 모두 출력해야하므로 프로그램의 시간복잡도도 O(2^n)

"""Solution code for "BOJ 31248. 3+1 하노이 탑".

- Problem link: https://www.acmicpc.net/problem/31248
- Solution link: http://www.teferi.net/ps/problems/boj/31248
"""


def move_rec(n, source, dest, temp, answer):
    if n == 1:
        answer.append(source + ' ' + dest)
        return
    move_rec(n - 1, source, temp, dest, answer)
    answer.append(source + ' ' + dest)
    move_rec(n - 1, temp, dest, source, answer)


def main():
    N = int(input())
    answer = []
    source, dest, temp = 'A', 'B', 'C'
    for i in range(N - 2, 0, -2):
        move_rec(i, source, dest, temp, answer)
        move_rec(2, source, 'D', temp, answer)
        dest, source = source, dest
    move_rec(1 if N % 2 == 1 else 2, source, 'D', temp, answer)

    print(len(answer))
    print('\n'.join(answer))


if __name__ == '__main__':
    main()