꾸준히 개발하기

이 난이도가 실버 2? 거짓말이라고 해달라....

재귀함수는 문제를 이해하고 점화식 도출해서 코드로 구현하는 그 일련의 과정이 감이 안오면 정말 손도 못 대겠더라. 끙끙 고민하다가 결국 다른 사람의 풀이를 보고 이해했다.

문제를 살펴보면 원반 N개를 해결하려면 원반 N-1개인 상황을 해결해야 한다. 즉, 다음의 과정을 도출해낼 수 있다.

1. N개의 원반이 주어지면 위에서부터 N-1개의 원반을 두번째 기둥으로 옮김
   현재 상태 -> 기둥 1에는 제일 큰 N번째 원반이 남아있으며 기둥 2에는 N-1개의 원반이 있다.
2. 기둥 1의 N번째 원반을 목표 지점인 기둥 3로 옮긴다
3. 기둥 2에 남아있는 N-1개의 원반을 목표 지점인 기둥 3로 옮기면 된다.

문제에서 20이 넘어가면 횟수만 출력하라 했는데, 재귀의 깊이가 너무 깊어질 수 있어 20이 넘어가면 단순히 값만 출력하라고 하는 듯 하다. 원판이 n개 일 때, 2^n -1(=2의 n승 빼기 1)번의 이동으로 원판을 모두 옮길 수 있다. 

이를 코드로 구현하면 다음과 같다.

import sys

input = sys.stdin.readline


# start -> end로 원반 disc개 이동
def hanoi(start, mid, end, disc):
    if disc == 1:  #
        print(start, end)  # 출력
    else:
        hanoi(start, end, mid, disc - 1)  # 기둥1 -> 기둥2 (n-1개를 잠시 이동)
        hanoi(start, mid, end, 1)  # 가장 큰 원반 기둥1 -> 기둥 3
        hanoi(mid, start, end, disc - 1)  # 기둥2 -> 기둥3


N = int(input())

print(2 ** N - 1)
if N <= 20:
    hanoi(1, 2, 3, N)

재귀... 재귀.... 이름도 귀신같아가지고 아주 무서운 놈이다 ...