하노이의 탑

하노이의 탑(백준 1914)

일일이 블록을 이동하며,
뭔가 규칙성을 찾는 방식을 사용하였다
(혹시 그래서 ‘수학적 귀납법’이 사용된다고 말하는 걸까??)

귀납적으로 생각한 과정은…
일단 하노이 탑의 가장 밑부분을 1 -> 3으로 옮겨야 하며
이 때 2번 의 탑에는 n - 1 의 하노이 탑이 생성된다
또한 2번의 탑의 마지막 밑부분을 빼려면 1에 n -2 의 하노이 탑이 생성
…
마지막으로 1 혹은 2에 남아있는 하노이의 탑이 3으로 옮겨가며 마무리된다

정리한 수학적 귀납법

하나의 원반 k는 자신 위에 존재하는 원반(k-1)을
방문하지 않은 곳(no visit)으로 보내고
k를 시작점(start) 목적지(to)로 옮긴다
이후 ‘k - 1’도 목적지(to)로 옮긴다

종료조건

자신이 아무것도 없다면 (n-1 이 0인 상황),
해당 함수를 진행할 이유가 없으므로 return

위의 내용대로 만들어진 함수는
가장 ‘밑부분’의 원반을 기준으로 반복적으로 원반을 찾아간다.
n에 사용된다면,
‘n-1 녀석을 ‘no visit’로 옮겨(함수)’
‘나(n)를 목적지(to)로 옮겨(print)’
‘n-1 녀석을 목적지(to)로 옮겨(함수)’

점화식

정의는 ‘이웃하는 두 항의 관계를 나타내는 식’

기본적인 점화식

  1. a(n+1) = a(n) + f(n)
  2. a(n+1) = a(n) * f(n)
  3. a(n+1) = c * a(n) + f(n)

변형 점화식(기본 점화식을 변형하여 만들 수 있음)

  4. a(n) + c = b(n)
  5. a(n+1) - a(n) = b(n)
  6. 1 / a(n) = b(n)

[출처 : 마인드맵수학]https://m.blog.naver.com/mindmapmath/221825770631

하노이의 점화식은 다음과 같이 생각하여 작성하였다
‘n-1 녀석을 ‘no visit’로 옮겨줘’ : a(n - 1)
‘나(n)를 목적지(to)로 옮겨줘’ : 1
‘n-1 녀석을 목적지(to)로 옮겨줘’ : a(n - 1)
따라서 ‘a(n) = 2 * a(n -1) + 1’

옮긴 횟수

위의 점화식을 참고하여
결국 자기자신을 2번 호출하기에
옮긴 횟수는 ‘2의 n승’ 같은 2의 제곱이라 생각하였다
2^ n - 1까지는 맞았으나
n 자신에 대해서는 한번만 옮기면 되므로 + 1을 해주어 완성하였다

  옮긴 횟수 = 2^(n-1) + 1

제출한 코드

def hanoiMove(start,to,novis,n):
    if(n < 1):
        return
    hanoiMove(start, novis, to, n-1) # k-1 녀석을 시작점에서 novis로 옮겨야 함 (이번에 to는 방문하지 않음)
    print(start,to)               # k 녀석을 시작점에서 목표로 옮김 
    hanoiMove(novis,to,start,n-1) # k -1 녀석을 novis에서 목표로 옮김

tryCount = int(input())
tryNum =pow(2,tryCount) - 1
print(tryNum)
if tryCount <= 20:
    # 첫번째 원반을 3번으로 옮기고 2번을 novisit로 두고 시작 (그래야 1일때도 통과)
    hanoiMove(1,3,2,tryCount)