BOJ 1914 (하노이 탑)

def hanoi(n, start, end, via):
	if n == 1:
		print(start, end)
	else:
		hanoi(n-1, start, via, end)
		print(start, end)
		hanoi(n-1, via, end, start)

n = int(input())
print((2**n)-1)
if n <= 20:
	hanoi(n,1,3,2)

문제를 봤을 때, 재귀적으로 풀면 된다는 생각은 들었지만 구현까지는 힘들었다. 이해하는데 엄청 도움이 된 링크를 첨부하겠다.

https://shoark7.github.io/programming/algorithm/tower-of-hanoi