불러오는 중
기둥 세 개와 크기가 모두 다른 원판 h개가 있다. 원판은 전부 출발 기둥에 크기 순으로 쌓여 있다. 한 번에 원판 하나만 옮기고, 큰 원판을 작은 원판 위에 놓을 수 없다.
원판 h개를 출발 기둥에서 도착 기둥으로 옮기는 순서는 세 단계로 나뉜다. 위의 h−1개를 중간 기둥으로 옮기고, 맨 아래 원판 하나를 도착 기둥으로 옮기고, 중간 기둥에 있던 h−1개를 도착 기둥으로 옮긴다. 첫 단계와 마지막 단계는 기둥의 자리만 바꾼 같은 문제이므로 재귀 호출로 처리한다.
원판을 옮기는 총 횟수와 옮기는 순서를 출력한다.
첫째 줄에 원판의 수 h가 주어진다. 둘째 줄에 출발 기둥, 도착 기둥, 중간 기둥의 이름이 이 순서대로 공백으로 구분되어 주어진다. 기둥 이름은 서로 다른 대문자 한 글자이다.
첫째 줄에 원판을 옮기는 총 횟수를 출력한다. 둘째 줄부터 옮기는 순서를 한 줄에 하나씩 출력한다. 각 줄은 출발 기둥 이름, 공백, ->, 공백, 도착 기둥 이름의 순서로 적는다.
1≤h≤10이다. 옮기는 횟수는 2h−1이다.
입력
3
A C B
출력
7
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
입력
1
P Q R
출력
1
P -> Q