백준 1914번 하노이탑 파이썬 (재귀)

백준 1914번 하노이탑 파이썬 (재귀)

참고: https://www.acmicpc.net/problem/1914
https://namu.wiki/w/하노이의 탑#fn-1

무엇?

세 개의 장대
첫 번째 장대에는 반경이 서로 다른 N개의 원판이 있음
각 원판은 반경이 큰 순서대로 쌓여있다.
다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮긴다.

1. 한 번에 한 개의 원판만 다른 탑으로 옮김
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 함
   이 작업을 수행하는데 필요한 이동 순서를 출력
   단, 이동 횟수 K는 최소

입력: 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)
출력

• 첫째 줄에 옮긴 횟수 K
• N이 20 이하인 입력에 대해서만, 둘째 줄부터 빈칸을 사이에 두고 A, B를 출력
• 두 정수 A B는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻

왜?

1주차 알고리즘 복습

어떻게?

내 코드

원판의 갯수가 몇개든 하노이탑을 옮기는 공통 과정을 찾음

1. N-1개 판을 보조 탑으로 옮김
2. 1개 판만 목적지 위치로 옮김
3. N-1개 판을 보조 탑에서 목적지 위치로 옮김
4. 판 하나를 옮길 때만 옮긴 위치 출력

import sys

inputN = int(sys.stdin.readline())


def hanoi(N: int, A: int, B: int, C: int):
    if (N == 1):
        print(A, C)
    else:
        hanoi(N-1, A, C, B)     # 처음 공통단계: A->B
        hanoi(1, A, B, C)       # 중간 공통단계: 하나만 A->C
        hanoi(N-1, B, A, C)     # 마지막 공통 단계: B->C


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

try-error

1. 재귀 종료 조건을 N <= 0 으로 설정 + 출력 조건도 또 그와 별개로 작성
   지금 코드보다 다소 복잡하고, 판이 여러개 일때도 옮긴 위치가 출력되는 에러
2. 다 옮기기도 전에 어떻게 옮긴 횟수를 출력하나?
   n개의 하노이탑을 옮기는데 필요한 횟수를 구하는 공식이 아래와 같이 알려져 있음

n번째 원반을 한쪽 기둥으로 옮기는 데 필요한 최소 횟수를 ​라고 하자. n+1번째 원반을 옮기려면(​을 구하려면) n번째 까지의 원반을 한쪽 기둥으로 옮기고(​를 더하고) n+1번째 원반을 비어있는 기둥에 옮기고(1을 더하고) n번째까지의 원반을 (n+1)번째 원반 위로 옮기면(​를 다시 더하면)된다.
따라서 , 이고 이 점화식에 의한 수열 ​의 일반항을 구해보면 가 나온다.

순서 상 옮긴 위치 출력 -> 옮긴 횟수 출력 이게 자연스럽다고 생각했는데, 그러려면 옮긴 횟수와 옮긴 위치를 변수에 담아 저장해야 했고, 그러다보니 메모리 초과로 실패함