[백준 11729] 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

"""
재귀는 종료 조건이 있는 반복 작업을 인풋 개수를 줄여 반복해나가는 것
종료 조건:
    블럭(=인풋 개수)이 1개면: 
        출발 위치에서 도착 위치로 옮긴 후 종료
반복 작업:
    (재귀) 마지막 블럭을 제외한 위의 모든 블럭을 임시 위치로 옮기고,
    마지막 블럭을 도착 위치로 옮긴 뒤
    (재귀) 임시 위치의 블럭을 도착 위치로 옮기기 
"""

def hanoi(block, one, two, three): # 각 인수로 남은 블럭수, 출발 위치, 임시 위치, 도착 위치 
    # 종료 조건 
    if block == 1: # 블럭(=n)이 1개면
        print(one, three)
    # 종료 조건이 아니면 재귀
    else:
        # 마지막 블럭을 제외한 위의 모든 블럭을 임시 위치로 이동 
        hanoi(block - 1, one, three, two)
        print(one, three) # 마지막 블럭을 도착 위치로 이동
        # 임시 위치로 옮겼던 블럭을 다시 도착 위치로 옮기
        hanoi(block - 1, two, one, three)

n = int(input())
print(2 ** n - 1) 
hanoi(n, 1, 2, 3)

처음에 하노이탑의 왼쪽부터 시작 위치, 임시 위치, 

https://jwmath.tistory.com/103

하노이 탑의 일반항을 구하기

 

 

# res = [0] # mutable 이뮤타불에 따라 전부 참조형이지만 값 불변되어 참조 못함 

 

immutable : int, float, str, tuple

mutable: list, dict