백준 11729 : 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

1. 코드설명

- n-1개의 원판을 1번 막대에서 2번 막대로 옮긴다.

- 남은 1개의 원판을 1번 막대에서 3번 막대로 옮긴다.

- 다시 n-1개의 원판을 2번 막대에서 3번 막대로 옮긴다.

 

이 매커니즘으로 재귀를 짠다.

 

2. 예

원판의 개수 n개를 입력하면 첫번째줄에 3번째로 모두 옮기기 위한 총 이동 횟수가 나오고

두번째줄부터는 원판이 어디서 어디로 이동했는가가 나온다.

 

3. 코드

# 11729

def hanoi(N, start, end):
    if N == 1:
        print(start, end)
        return
    
    hanoi(N-1, start, 6-start-end)
    print(start, end)
    hanoi(N-1, 6-start-end, end)

N = int(input())
print(2**N-1)
hanoi(N, 1, 3)

 

 

1. n-1개의 원판을 start에서 6-start-end로 옮긴다.

2. 마지막 원판을 start에서 end로 옮긴다.

3. 다시 n-1개의 원판을 end로 옮긴다.