[2021 SCPC 2차 예선]
이 문제에서는 전통적인 하노이 탑 문제의 약간 다른 변형에 대하여 다룬다.
먼저 3개의 기둥이 있고 각각을 1번, 2번, 3번으로 지칭한다. 1번 기둥에 N개의 서로 다른 크기의 디스크가 작은 것은 위에 큰 것은 아래에 쌓여 있다. 이 디스크들을 모두 3번 기둥으로 옮기는 것이 목표이다. 단, 어떤 상황에서도 큰 디스크가 작은 디스크 위에 올라가서는 안 된다.
여기까지는 기존의 하노이 탑 문제와 다를 것이 없다. 다른 부분은 디스크의 이동에 대한 것이다. MOVE(X, Y)는 X번 기둥에서 다른 Y번 기둥으로의 이동을 의미하며, 이동 전 X번 기둥에 쌓여있는 디스크의 개수를 x 개, Y번 기둥에 쌓여있는 디스크의 개수를 y 개라고 할 때, X번 기둥의 위에서 \(\lfloor {x\over2} \rfloor +1\)번째 디스크를 빼내어, Y번 기둥에 삽입하여 위에서 \(\lfloor {(y+1)\over2} \rfloor +1\)번째가 되도록 하는 연산을 의미한다.
말하자면, MOVE(X, Y)는 X번 기둥의 “가운데” 위치의 디스크를 빼내어 Y번 기둥에 끼워 넣어 Y번 기둥의 “가운데”에 위치하도록 하는 연산이다.
이때, 어떤 기둥의 “가운데” 위치는 그 기둥에 쌓여있는 디스크의 개수를 x라 할 때, 위에서 \(\lfloor {x\over2} \rfloor +1\)번째 위치를 말한다.
MOVE 연산의 최대 사용 횟수 M이 주어질 때, 최대 M번 이내의 MOVE 연산 만을 사용하여 1번 기둥에 N개의 디스크를 모두 3번 기둥으로 옮기는 방법을 출력하는 프로그램을 작성하시오.
N의 값은 26이하인 값으로, 작성한 프로그램이 스스로 지정한다.
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T 가 주어지고,
이후 차례로 T 개의 테스트 케이스가 주어진다. (T=1)
각 테스트 케이스의 첫 줄에 정수 M이 주어진다. (M=980,403).
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.
두번째 줄에, 1이상 26 이하의 정수 N을 출력하고, 세번째 줄에 N개의 디스크를 1번 기둥에서 3번 기둥으로 옮기는 방법을 {A, B, C, D, E, F}로 이루어진 문자열로 출력한다. 이 문자열의 각 문자는 다음과 같은 의미를 가진다.
A = MOVE(1, 2), B = MOVE(1, 3), C = MOVE(2, 1), D = MOVE(2, 3), E = MOVE(3, 1), F = MOVE(3, 2)
| 입력 |
|---|
| 1 980403 |
| 출력 |
|---|
| Case #1 3 AABDD |