1914 하노이 탑

하노이 탑 문제는 가장 유명한 재귀호출 문제 중 하나다

가장 왼쪽에 있는 원판들을 그대로 가장 오른쪽에 있는 원판으로 옮기는 작업이다. 중간에 있는 기둥을 사용해서 말이다

 

https://skmagic.tistory.com/257

과정은 대략 이렇다

1. 1번 기둥에 있는 원판 중 n-1개를 2번 기둥으로 옮긴다

2. 1번 기둥에 남은 가장 큰 원판을 3번 기둥으로 옮긴다

3. 2번 기둥에 있던 n-1개의 원판을 다시 3번을 목표로 옮긴다

 

정리하면 시작점과 도착점이 있고, 도달하기 위한 중간점을 이용해야만 한다. 원판이 모두 도착점에 도달할 때까지 재귀를 이용하면 된다

수학적으로 증명된 사실이지만 하노이탑의 총 이동횟수는 2^n-1이며, n이 64가 넘어갔을 때는 string을 이용해 큰 수 연산을 해야만 한다. 2^n은 10의 배수가 절대로 나올 수 없으므로 마지막 수만 1만 뺀다면 정답을 구할 수 있다

 

문제: https://www.acmicpc.net/problem/1914

깃허브주소: https://github.com/surinoel/boj/blob/master/1914.cpp