6008 : 재귀 심화 — 하노이 경로 추적
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
하노이 탑(Hanoi Tower) 게임에서 $N$개의 원판을 기둥 A에서 기둥 C로 옮기는 최적의 이동 과정을 재귀적으로 탐색하십시오.
원판의 개수 $N$이 $15$ 이하인 경우에는 원판의 전체 이동 경로를 출력하고, $15$를 초과하는 경우에는 시간 및 출력 초과를 방지하기 위해 이동의 총 횟수만 출력합니다.
[제약 조건]
• 원판 수 $N$: $1 \le N \le 20$ (정수)
• 이동 단계 수는 $2^N - 1$개이며, 모두 출력합니다.
원판의 개수 $N$이 $15$ 이하인 경우에는 원판의 전체 이동 경로를 출력하고, $15$를 초과하는 경우에는 시간 및 출력 초과를 방지하기 위해 이동의 총 횟수만 출력합니다.
[제약 조건]
• 원판 수 $N$: $1 \le N \le 20$ (정수)
• 이동 단계 수는 $2^N - 1$개이며, 모두 출력합니다.
입력 설명
첫째 줄에 원판의 개수 $N$이 주어집니다.
[제약 조건]
• $1 \le N \le 25$
출력 설명
$N \le 15$인 경우:
첫째 줄에 총 이동 횟수 $2^N-1$을 출력하고, 둘째 줄부터 출발기둥->도착기둥(예: A->C) 형태로 이동 경로를 출력합니다.
$N > 15$인 경우:
첫째 줄에 총 이동 횟수 $2^N-1$만 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
7
A->C
A->B
C->B
A->C
B->A
B->C
A->C도움
하노이 재귀: $k-1$개를 보조 기둥으로 이동 $\to$ 1개를 목표 기둥으로 이동 $\to$ $k-1$개를 목표 기둥으로 이동.