[BOJ] 재귀 - 하노이 탑 이동 순서 - Python

11729: 하노이 탑 이동 순서

# 11729: 하노이 탑 이동 순서
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'''
1부터 (n-1)번째 원판을 중간 기둥(mid)에 옮긴다. (1)
n번째 원판을 목적지(end)에 둔다. - (2)
중간 기둥에 있는 (n-1)개의 원판을 다시 목적지(end)로 옮긴다. - (3)


n-1개 원판을 옮기는 과정을 recursion 한다고 접근한다. (재귀가 필요한 부분)
'''
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
n = int(input())

print((2**n) - 1) # 옮긴 횟수 K

# second는 보조 역할, N-1 개의 작은 순 원판을 놓을 자리, third는 가장 큰 원판을 놓을 자리
def Move_Hanoi(N, start, end, mid) : # n개의 원판을 start에서 end로 간다. (mid는 보조 자리 역할, 즉 2번)
  if N == 1 : # 종료조건, 원판이 단 하나 남았을때 종료
    print(start, end) # 1개를 start에서 end로 간다.
    return
  else :
    Move_Hanoi(N-1, start, mid, end) # n-1개의 작은 원판(가장 큰 밑바닥 원판 제외)를 보조(mid)로 옮긴다.
    print(start, end) # 위 과정에서 남은 가장 밑바닥 원판을 end로 옮긴다.
    Move_Hanoi(N-1, mid, end, start) # 보조에 있던 n-1개를 목표지점(end)로 옮긴다.

Move_Hanoi(n, 1, 3, 2)

 

1부터 (n-1)번째 원판을 중간 기둥(mid)에 옮긴다. (1) n번째 원판을 목적지(end)에 둔다. - (2) 중간 기둥에 있는 (n-1)개의 원판을 다시 목적지(end)로 옮긴다. - (3)

n개의 원판일 경우

옮긴 횟수 K 의 수 = 1 + 2*A(n-1) 

가장 큰 원판을 옮긴 횟수는 = 1 ······ (1)

나머지 원판들을 중간으로 옮긴 횟수는 = A(n-1) 이라 하자. ······(2)

마지막으로 (n-1)개를 다시 목적지로 옮긴 횟수를 A(n-1) 이라 하자. ······ (3)

 

원판의 총 개수(N)	옮긴 횟수 (K)
1	1
2	1 + 2*A(1)
3	1 + 2*A(2)
4	1 + 2*A(3)
5	1 + 2*A(4)
······	······
n-1	1 + 2*A(n-2)
n	1 + 2*A(n-1)

A(n) = 1 + 2*A(n-1) ······ (4)위 식을 봤을때, (1) 과정 - 1회, (2),(3) 과정 n-1개 옮기는걸 총 2회 라는 것을 느낄 수 있죠?위 식 (4) 에서 양변에 1을 더합니다.

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

A(n)+1 = 2(1+A(n-1))

A(n)+1 = b(n) 이라 놓으면,

b(n) = 2*b(n-1)

첫항이 b(1) = A(1)+1 = 2 이고, 공비가 2인 공비 수열이라고 말할 수 있죠.

따라서 b(n) = A(n)+1 = 2^n

A(n)+1 = 2^n -> A(n) = 2**n - 1 이 됩니다.

사실 1 3 7 ~~ 보고 규칙성을 직관으로 찾아도되는데 이렇게 수열 점화식을 이용해서 접근하면 더 이해가 잘 되실겁니다.

 

재귀 문제를 풀 때 항상 생각하셔야 할 2가지는,

1. 재귀 종료 조건

위 문제에서는 1개의 원반이 남아 옮길때까지 입니다.

2. 문제의 정의

(1) ~ (3) 과정을 말합니다.

문제를 정의할때 계속 반복되는 느낌을 작은 문제로 접근해서 이해하고 전체를 소분해서 푼다는 느낌으로

저 같은 경우에는 수학의 부분집합 개념을 계속 반복한다는 느낌인거같아요.