시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 623 130 (21%) 114
문제
유명한 하노이 문제에 대해서 생각해보자. 우리에게 주어진 임무는 탑의 개수 n 이 주어졌을 때, 움직이는 원판의 개수가 가장 적은 경로를 출력하는 것이다. 하노이 설명 1. 세 기둥(A, B, C) 으로 이루어져 있고 A에 있는 모든 원판을 C 에 옮기는 것이 목표다. 2. 한번에 한 원판만 움직일 수 있다. 3. 반드시 큰 원판 위에 작은 원판이 올라가야 한다. 4. 각 탑의 맨 위에 있는 원판만 옮길 수 있다.
입력
첫재 줄에 원판의 수 n이 주어진다. (1 ≤ n ≤ 20)
출력
A에 있는 원판 n개를 C에 옮기는 최소 횟수를 출력하고 그 다음 줄부터 몇번째 원판이 어디에서 어디로 옮기는지 출력하시오. (예제 참고)
힌트
#### 입력 예제 ``` 4 ``` #### 출력 예제 ``` 15 1 : A -> B 2 : A -> C 1 : B -> C 3 : A -> B 1 : C -> A 2 : C -> B 1 : A -> B 4 : A -> C 1 : B -> C 2 : B -> A 1 : C -> A 3 : B -> C 1 : A -> B 2 : A -> C 1 : B -> C ```