이 문제는 하노이의 탑에 대해 모르면 풀기 힘들다. 모른다면 아래 링크를 클릭하자.
하노이의 탑이란? Click
수학을 어려워하는 피에로는 n 개의 고리가 있는 하노이의 탑의 최소 이동횟수가 2n-1 이라는 것을 이해하지 못해서 나머지 수업을 받았다. 하지만, 피에로의 생각을 들어보면 꼭 틀린 것 같지는 않다.
“한 손은 고리를 옮기고 다른 손에는 고리 하나를 들 수 있으니 그것보다 더 적게 걸리지 않을까?”피에로의 생각대로 한다면, 고리 4개를 옮기는데 걸리는 원래 횟수는 15회이지만, 다음 과정으로 횟수가 9회로 줄어들게 된다는 것을 알 수 있다. (꼭대기의 수들만 표시하였고, []는 손에 들고 있는 것이다.)
1 0 0 [0] 2 0 1 [0] 3 2 1 [0] 3 1 0 [0] 4 1 0 [3] 0 1 4 [3] 0 1 3 [0] 0 2 3 [1] 0 0 2 [1] 0 0 1 [0]우리는 이 피에로의 방식대로 하노이의 탑을 옮겨서 개선된 하노이의 탑의 최소횟수를 구하는 것이다.
입력 3 출력 5(7) 입력 4 출력 9(15)
출처:Fate