하노이의 탑

세 개의 막대 위에 길이가 서로 다른 여섯 종류의 원판이 올라가 있다. 원판들은 반지름이 큰 원판이 아래에 오도록 아래와 같이 쌓여 있다.

위 그림은 원판의 초기 배치를 나타낸다. 여기서 원판 하나를 들어 다른 막대 위로 올려다놓는 방법으로 원판을 옮길 수 있다. 이 과정에도 무조건 반지름이 큰 원판이 아래에 온다는 조건이 만족되어야 한다.

그리고, 이번에는 원판을 움직일 때 추가로 지켜야 하는 사항이 있다. 세 개의 막대가 차례로 1, 2, 3번 막대라고 하자. 이 때,

• 1번 막대에서 2번 막대로
• 2번 막대에서 3번 막대로
• 3번 막대에서 1번 막대로

원판을 움직이는 것만 허용된다. 이 사항을 지키면서 원판을 아래와 같은 상태로 만들어야 한다.

원판을 위 상태로 만들고 나서 제출 버튼을 눌러야만 점수를 받을 수 있다. 어떤 상태에서든 제출 버튼을 누르면 현재까지 옮긴 원판의 상태를 저장할 수 있다. 원판을 움직이는 횟수에 대한 제한은 없으므로, 움직임의 횟수를 최소화할 필요는 없다. 언제든 '다시 하기' 버튼을 누르면 처음부터 다시 시작할 수 있으며, '되돌리기' 버튼을 누르면 방금 한 이동을 되돌릴 수 있다. 원판을 위와 같은 상태로 만들었다고 별도로 알려주지 않음에 유의하라.

문제 형식

인터랙티브

출처

• KOI 2021 1차대회 고등부 1교시 14번
• KOI 2021 1차대회 중등부 1교시 14번