백준 11729. 하노이탑 - 실버 2

하노이탑 알고리즘

A, B, C 기둥이 있고, A의 원반을 전부 C로 옮기는 것이 목표

1. n-1 개의 원반을 B로 옮긴다.

2. A에 남은 원반을 C로 옮긴다.

3. B에 있는 n-1 개의 원반을 C로 옮긴다.

* n이 1일 때에는 목적지로 바로 이동시켜준다.

import sys
sys.stdin = open("sample.txt", "r")

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

stick = []
stick += [i for i in range(n,0,-1)], [],[]

def hanoi(n, A, B, C):
    # A에서 C로 이동시키고, B를 보조로 사용
    if n == 1:
        print(f'{A} {C}')
        # C.append(A.pop())
        return

    hanoi(n-1, A, C, B)
    hanoi(1, A, B, C)
    hanoi(n-1, B, A, C)

print(2**n-1)
hanoi(n, 1,2,3)

 

참.. 이런거 어떻게 생각해내는 건지.. 갈 길이 멀다