[JAVA] 백준 1914번 하노이 탑

 

분류 : 재귀 (Recursion)

URI : www.acmicpc.net/problem/1914

---

 

[ 이동 횟수 구하기 ]

 

$ a_n = a_{n-1} + 1 + a_{n-1} $

 

n개의 탑을 1번에서 3번으로 이동하려면

1.  n-1개를 1 -> 2 이동 
2. 남은 1개를 1 -> 3 이동
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} $ 은 첫째항이 2, 등비가 2인 등비 수열이 된다.

 

따라서, $ b_n = 2*2^{n-1} $ 이므로 $ b_n = 2^n $

$ a_n + 1 = 2^n $

이동 횟수는 $ a_n = 2^n - 1 $ 이 된다.  

 

 

[ 제출 코드 ]

 

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static StringBuilder sb = new StringBuilder();

    public static void hanoi(int num, int from, int by, int to) {
        if(num == 1) {
            sb.append(from + " " + to + "\n");
        } else {
            hanoi(num-1, from, to, by); // 1번에서 2번으로
            sb.append(from + " " + to + "\n");
            hanoi(num-1, by, from, to); // 2번에서 3번으로
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        BigInteger res = new BigInteger("1");
        int N = scan.nextInt();
        if (N<=20) { 
            hanoi(N, 1, 2, 3);
            sb.insert(0, (int)(Math.pow(2, N) - 1) + "\n");
            System.out.print(sb);
        } else { // 20 초과하면 BigInteger로 이동 횟수만 출력
            for(int i=0; i<N; ++i) {
                res = res.multiply(new BigInteger("2")); // 2의 N 제곱
            }
            res = res.subtract(new BigInteger("1")); // 빼기 1
            System.out.println(res);
        }
    }
}