문제
A, B, C 세개의 기둥이 있을 때, N개의 원판을 A번 기둥에서 C번 기둥으로 이동하는
일반적인 하노이 규칙에 다음과 같이 3번 규칙을 추가한 경우를 보자.
1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있을 수 없다.
3. 가능한 가장 긴 단순 경로(simple path)를 이용하여 원판을 옮겨야 한다.
(단순 경로란 이전과 같은 상태를 다시 거치지 않는 경우를 말한다.)
예를 들어 아래 그림과 같이 A번 기둥에 2개의 원판이 쌓여 있는 경우를 생각해 보자.
위 모습을 순서쌍으로 나타내면 (12, 0, 0) 이라고 하자.
이를 이용하여 우리가 원하는 최종 상태를 나타내면 (0, 0, 12) 이다.
위 3가지 규칙에 따라 가장 긴 단순 경로를 구한 예는 다음과 같다.
( 2, 1, 0) 1번 원판이 A기둥에서 B기둥으로 1 : A->B
( 2, 0, 1) 1번 원판이 B기둥에서 C기둥으로 1 : B->C
( 0, 2, 1) 2번 원판이 A기둥에서 B기둥으로 2 : A->B
( 0,12, 0) 1번 원판이 C기둥에서 B기둥으로 1 : C->B
( 1, 2, 0) 1번 원판이 B기둥에서 A기둥으로 1 : B->A
( 1, 0, 2) 2번 원판이 B기둥에서 C기둥으로 2 : B->C
( 0, 1, 2) 1번 원판이 A기둥에서 B기둥으로 1 : A->B
( 0, 0,12) 1번 원판이 B기둥에서 C기둥으로 1 : B->C
가장 긴 단순 경로는 8
모든 원판이 A번 기둥에 순서대로 쌓여 있을 때,
위 규칙에 따라 C번 기둥으로 모두 이동하는 과정을 순서대로 출력하는 프로그램을 작성하시오.
입력
첫 행에 정수 N이 주어진다.( 1 <= N <= 10,000,000)
출력
출력 결과를 참고하여 각 줄에 이동하는 원판과 기둥정보를 출력한다.
출력결과에서 100줄을 초과하는 경우는 100줄까지만 출력한다.
마지막 줄에는 가장 긴 단순경로의 수를 10억7로 나눈 나머지를 출력한다.
예제
2
1 : A->B
1 : B->C
2 : A->B
1 : C->B
1 : B->A
2 : B->C
1 : A->B
1 : B->C
8
출처
JKJeong
로그인해야 코드를 작성할 수 있어요.