백준 알고리즘 1914번 문제 - 하노이 탑2

1914번: 하노이 탑

어제도 하노이 탑 문제(11729번)를 풀었는데, 오늘은 문제에서의 조건이 조금만 다른 하노이 탑 문제를 리뷰한다.

이 문제에서는 20이하의 입력일 때는 옮긴 횟수와 그 과정까지 출력이지만, 20을 넘어서면(20< n <= 100) 재귀 과정이 너무 깊어지기에 옮긴 횟수만 출력하는 문제이다.

쉽게 풀 수 있겠다 생각했지만 재귀가 너무 깊어져서 시간 초과가 계속 났다. 어떻게 하면 될까 고민해 본 결과, 잘 생각이 나지 않았다. 다른 블로거 분들의 문제 풀이를 보니, 문제가 말하고자 하는 것이 이는 재귀를 통해 횟수를 구하는 것이 아닌 일종의 점화식을 구하라는 것을 문제에서 암묵적으로 힌트를 주는 것임을 알 수 있다.

규칙을 알아보자,

n 이 1 일 때, 1

n이 2일 때, 3

n이 3일 때, 7

n이 4일 때, 15

.. => 즉 2^n - 1 이 점화식임을 알 수 있다.

심각하게 생각하지말고 센스를 길러보자^^

참고: https://bgspro.tistory.com/6