[백준] 하노이 탑 이동 순서 - Python

11729번: 하노이 탑 이동 순서

POINT

등비수열

등비수열 공식

재귀 함수 (Recursion function)

함수 안에서 함수 자신을 또 호출하여 사용하는 함수

하노이 탑

n개의 원반을 옮긴다면,

 

1단계. 제일 큰 원반을 제외한 나머지 (n-1)개의 원반을 2번으로 옮긴다.

• 이동 횟수: f(n-1) 번

1단계

2단계. 제일 큰 원반 1개를 3번으로 옮긴다.

• 이동 횟수: 1번

2단계

3단계. (n-1)개의 원반을 3번으로 옮긴다.

• 이동 횟수: f(n-1) 번

3단계

 

결론. 다음과 같은 식이 만들어지며, 등비수열로 풀면 된다.

f(n) = 2 * f(n-1) + 1

따라서, f(n) = 2^n - 1

풀이

def hanoi(n, start, end):
    if n == 1:
        print(start, end)
    
    else:
        hanoi(n-1, start, 6-start-end) # (n-1)개를 남은 자리로 옮긴다.
        print(start, end) # 가장 큰 1개를 목적지로 옮긴다.
        hanoi(n-1, 6-start-end, end) # (n-1)개를 목적지로 옮긴다.
    
n = int(input())
print(2**n - 1)
hanoi(n, 1, 3)