[ BAEKJOON ] No. 11729 : 하노이 탑 이동 순서

문제 )

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

11729번: 하노이 탑 이동 순서

 

풀이 )

 

N개의 판을 옮기는 경우 

N개의 판을 옮기는 경우

< 순서 >

1. 1번째 판 ~ (N-1)번째 판 까지 전부 2번으로 옮겨주기
2. N번째 판을 3번으로 옮겨준다 
3. 1번째 판 ~ (N-2)번째 판 까지 전부 1번으로 옮겨주기
4. (N-1)번째 판을 3번으로 옮겨준다 
.
.
.

가 계속 반복된다 
그러므로 재귀함수를 이용해서 알고리즘을 짜 보았다. 

(N-1) 개를 2번으로 옮기고 N번째 판을 3번으로 옮긴다. 
후에 (N-1) 개의 판을 2번에서 3번으로 옮긴다. 

 

✔ 하노이 탑의 이동 횟수 구하는 법
       : (2의 n제곱 )-1    = 2^n -1

 

 

- python code

def Hanoi(N, start, mid, end ):
    if N==1:
        print(start, end)
    else:
        Hanoi(N-1,start,end,mid)  # start에서 end를 거쳐 mid로 보내기
        print(start,end)
        Hanoi(N-1,mid,start,end) # mid에 있던걸 start를 거쳐 end로 보내기 


N=int(input())

# 횟수는 : 2^n-1
count= (2**N)-1
print(count)
Hanoi(N,1,2,3)