백준 11729 하노이탑 이동 순서 문제 풀이

하노이탑은 결국, n-1개의 블록을 1번 기둥에서 2번 기둥으로 옮기는 것 + n번째 블록을 1번 블록에서 3번 블록으로 옮기는 것 + n-1개의 블록을 2번기둥에서 3번 기둥으로 옮기는 것 으로 정의된다.

총 이동 횟수는 2^n  - 1 번 이다.

각 라인을 그때마다 출력한느 것이 아니라, StringBuffer를 이용해 저장한 후 마지막에 한번에 출력해야 시간초과가 안난다.

import java.util.*;
public class Main{
	private static StringBuffer sb = new StringBuffer();
	private static void f(int n,int from, int tmp, int to) {
		if(n==1) {
			sb.append(from+" "+to+"\n");
		}else {
			f(n-1,from,to,tmp);
			sb.append(from+" "+to+"\n");
			f(n-1,tmp,from,to);
		}
	}
	
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        int count = (int)Math.pow(2, n)-1;
        System.out.println(count);
        f(n,1,2,3);
        System.out.print(sb.toString());
    }
}