백준 1914번 하노이 탑 (JAVA)

https://www.acmicpc.net/problem/1914

1914번: 하노이 탑

 

저는 재귀를 통해 문제를 풀었습니다.

시작 가운데 목표 지점을 1,2,3이라 할 때 1에서 먼저 맨 밑에 제외하고 나머지는 2에 놓고, 맨 밑을 3에 넣고 2에 놓은 것을 3에 넣어야합니다. 이를 재귀적으로 풀어 문제를 풀었고, 20 이상인 경우에는 공식을 통해 문제를 풀어 문제를 해결하였습니다.

 

package BOJ.etc;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class BOJ_1914 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if(n <= 20){
            StringBuilder sb = new StringBuilder();
            int result = cal(n,1,2,3,sb);
            System.out.println(result);
            System.out.println(sb);
        }else{
            BigInteger result = new BigInteger("1");
            for(int i = 0 ; i < n ; i++){
                result = result.multiply(new BigInteger("2"));
            }
            result = result.subtract(new BigInteger("1"));
            System.out.println(result);
        }

    }
    private static int cal(int n, int start, int temp, int end,StringBuilder sb) {
        if(n == 0){
            return 0;
        }
        int result = 1;
        result += cal(n-1,start,end,temp,sb);
        sb.append(start + " " + end + "\n");
        result += cal(n-1,temp,start,end,sb);
        return result;
    }
}