재귀 - 백준11729 하노이 탑 이동 순서

그 유명한 하노이 탑 문제
하노이 탑의 풀이는 다음과 같다

1. start의 N-1개의 블록을 tmp로 옮긴다.
2. start의 1개의 블록을 end로 옮긴다.
3. tmp의 N-1개의 블록을 end로 옮긴다.
   이것을 재귀적으로 반복한다.

이를 코드로 옮기면 다음과 같다.

import java.io.*;
import java.util.*;

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

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String start = "1";
        String tmp = "2";
        String end = "3";
                
        hanoiTower(n, start, tmp, end);
                
        System.out.println(time + "\n" + sb);
    }
    
    static void hanoiTower(int n,String start,String tmp,String end){
        if(n <= 1){
            sb.append(start + " " + end + "\n");
            time++;
            return;
        }
        //1. start의 N-1개의 블록을 tmp로 옮긴다.
        hanoiTower(n-1, start, end, tmp);
        //2. start의 1개의 블록을 end로 옮긴다.
        hanoiTower(1, start, tmp, end);
        //3. tmp의 N-1개의 블록을 end로 옮긴다.
        hanoiTower(n-1, tmp, start, end);
    }
}

* System.out.println()을 사용하면 시간초과가 발생한다. -> StringBuilder 사용