11729 하노이 탑 이동순서

1. 하노이 탑 이동 순서

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	5754	2903	2182	51.878%

1.1. 문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.(중간 과정 역시 그래야함)

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

1.2. 입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

 

1.3. 출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

하노이의 탑은 공식이 있기 때문에 공식대로 푸는 것을 선호한다.

재귀호출로

123으로 시작해서

n-1 132

(경로저장)

n-1 213

을 계속 호출해주다가 n이 1일때 (경로저장)

하여 경로를 출력해주면된다.

아래는 소스이다.

import sys

sys.stdin = open("input.txt","r",encoding="utf-16")

num_of_circle = int(input())

cnt=0

moving = []

def move(n, one_slot, second_slot, third_slot):

if n == 1:

moving.append([one_slot,third_slot])

cnt= cnt+1

else:

move(n-1, one_slot, third_slot, second_slot)

moving.append([one_slot,third_slot])

cnt= cnt+1

move(n-1, second_slot, one_slot, third_slot)

move(num_of_circle,1,2,3)

print(cnt)

for i in moving:

print(i)

한번 누르면 2시간동안 보이지 않아요 ㅎㅎ 이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.

원치 않을 경우 를 눌러주세요