====== 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)


===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_3}}