[ Python ] 백준 11729 - 시간초과 해결!!

* 문제
https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

[ 해결 원리 ]
하노이탑 개념에 대해 그림으로 쉽게 설명해두었으니 참고하면 좋을 것 같다 :)
https://mminky.tistory.com/116

[ C ] 분할정복 - 하노이탑 (a divide-and-conquer algorithm for the Towers of Hanoi problem)

[ 코드 ]
**하노이탑 파이썬 - 시간초과가 떴다면**
print(count) 대신 print(2**n - 1) 를 해라!
-> 하노이탑의 총 옮긴 횟수는 2^n - 1으로 정해져 있다.
(하지만 개인적으로 옮길 때 마다 count를 증가시켜서 총 count를 출력하는 게 맞다고 생각한다.
근데 그렇게 하면 시간 초과가 된다..)

import sys input=sys.stdin.readline n = int(input()) #count = 0 #옮긴 횟수 #ans='' def hanoi(disk_num,from_peg,to_peg,tmp_peg): global count,ans if(disk_num==1): print(from_peg,to_peg) # ans += '{} {}\n'.format(from_peg,to_peg) # count += 1 return hanoi(disk_num-1,from_peg,tmp_peg,to_peg) print(from_peg,to_peg) # ans += '{} {}\n'.format(from_peg, to_peg) # count += 1 hanoi(disk_num-1,tmp_peg,to_peg,from_peg) print(2**n - 1) #count를 하니 시간 초과 뜸 # (처음)1 에서 (최종)3으로 이동함 # 2는 거치는 곳일 뿐! hanoi(n,'1','3','2') #print(count) #print(ans)

[ 결과 ]
와.. 진짜 시간초과 너무한거 아니냐고....
몇 번을 시도해서 결국 통과되었다.. 너무해..