[분할정복] 백준 11729번 하노이탑

1. 백준 11729번 문제 설명


입력)

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력)

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

2. 문제 풀이


하노이탑 알고리즘에 대한 설명과 pseudo 코드는 이전 포스팅에 있으니 참고하시길 바랍니다.

이전 포스팅에서 추가된 부분은 출력 결과 첫 번째 줄에 옮긴 횟수 K를 출력해야된다는 점입니다.

하노이탑의 최소 이동 횟수는 고1 때 배운 점화식을 활용해서 구할 수 있습니다.

하지만 점화식을 까먹은 문과생은....(나ㅎㅎ) 이걸 다시 공부합니다...

n개 원반의 최소 이동 횟수를 a_n이라고 가정하면, n-1개의 원반을 보조 기둥으로 이동한다음 마지막 원반을 이동하고, n-1개의 원반을 다시 목표지점으로 이동한다. 이를 수식으로 표현하면 다음과 같습니다.

a_n = a_(n-1) + 1 + a_(n-1)

a_n = 2a_(n-1) + 1

이 점화식을 풀기 위해서 양변에 1을 더합니다.

a_n + 1 = 2(a_(n-1) + 1)