분류 : 재귀 (Recursion) URI : www.acmicpc.net/problem/1914 [ 이동 횟수 구하기 ] $ a_n = a_{n-1} + 1 + a_{n-1} $ n개의 탑을 1번에서 3번으로 이동하려면 n-1개를 1 -> 2 이동 남은 1개를 1 -> 3 이동 n-1개를 2 -> 3 이동 $ a_n = 2a_{n-1} + 1 $ $ a_{n+1} = 2a_n + 1 $ 양 변에 1을 더하면 $ a_{n+1} + 1 = 2a_n + 1 + 1 $ $ a_{n+1} + 1 = 2(a_n + 1) $ $ a_n + 1 $ 을 $ b_{n} $ 이라고 하면 $ b_{n} = a_n + 1 $ $ b_{n+1} = 2b_n $ $ a_1 = 1 $ 이므로 $ b_1 = 2 $ $ b_{n} $..