파이썬 백준 1914 하노이 탑

a = [] def hanoi1to2(n) :     if n == 1 :         a.append('1 2')     else :         hanoi1to3(n-1)         a.append('1 2')         hanoi3to2(n-1) def hanoi1to3(n) :     if n == 1 :         a.append('1 3')     else :         hanoi1to2(n-1)         a.append('1 3')         hanoi2to3(n-1) def hanoi2to1(n) :     if n == 1 :         a.append('2 1')     else :         hanoi2to3(n-1)         a.append('2 1')         hanoi3to1(n-1) def hanoi2to3(n) :     if n == 1 :         a.append('2 3')     else :         hanoi2to1(n-1)         a.append('2 3')         hanoi1to3(n-1) def hanoi3to1(n) :     if n == 1 :         a.append('3 1')     else :         hanoi3to2(n-1)         a.append('3 1')         hanoi2to1(n-1) def hanoi3to2(n) :     if n == 1 :         a.append('3 2')     else :         hanoi3to1(n-1)         a.append('3 2')         hanoi1to2(n-1) n = int(input()) if n < 21 :     hanoi1to3(n)     print(len(a))     for i in a :         print(i) else :     print(pow(2, n) - 1)

n개의 판을 기둥 1에서 기둥 3으로 움직이는 것은

n-1개의 판을 기둥 1에서 기둥 2로 옮겨두고, n번째 판을 기둥 1에서 기둥 3으로 움직인 뒤

기둥 2에 둔 n-1개의 판을 다시 기둥 3의 n번째 판 위로 움직이는 과정이다.

한쪽 기둥 n-1개의 덩어리를 치우고 마지막 판을 옮긴 뒤 다시 덩어리를 옮기니 점화식은

a_(n-1) + 1 + a_(n-1) = a_n이 되고, 이의 일반항은 2^(n-1) - 1이다.

 

1. 판의 이동정보를 list에 저장하는, 서로가 서로를 정의하는 3*2개의 재귀함수를 정의한다.

2. list에 저장된 기록이 판의 이동경로이고, list의 길이가 총 이동횟수가 된다.

 

n이 20이상인 경우 과정을 출력하지 말라 주어졌는데, 실제로 함수를 돌리고 list 출력만 생략하니 메모리 초과가 떴다.

이건 더 줄일래야 줄일 것도 없어서 그냥 n이 20이상의 경우에는 함수를 실행하지 않고 일반항을 출력하게 했다.

 

주어진 조건내 최악의 경우 2^100번이상의 연산을 해야하는데 이게 제한시간 6초안에 될리는 없으니, 야매같아보이지만 아마 이렇게 거르는게 맞는 것 같다.