백준 11729 하노이 탑 이동순서 - python

 

출처 :

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

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단계 / 2단계/ 3단계 나눠서 생각을 한다.

 

1단계 : 1번에 맨 밑을 꺼내기 위해서는 그 위에 모든 것이 2번에 있어야한다. 

2단계 : 1번 맨 밑을 3번으로 옮긴다.

3단계 : 2번에 있는 것을 3번으로 옮긴다. 

 

이해가 안 갈 것 같아 추가 적으로 설명을 하면

예로 n = 4라고 하자.

그러면 이것의 4번째 를 꺼내기 위해선 2번에 1,2,3이 적재되있어야한다. (1단계) 

4를 3번칸으로 옮겨준다(2단계)

2번에 있는 모든것을 3번으로 옮겨 줘야 한다. 

 

어렵다..