[Java] 백준 11729 : 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

---

import java.util.*;

public class Main {
	
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int N=sc.nextInt();

		/*하노이 횟수 구하는 공식
			- hanoi(N)=hanoi(N-1)+1
			- a(n) = 2^n -1
		*/
		sb.append((int)(Math.pow(2, N)-1)).append("\n");
		
		Hanoi(N,1,2,3);
		System.out.println(sb);
	}// main()
	
	static void Hanoi(int n,int start, int mid, int end) {
		if (n == 1) {
			sb.append(start + " " + end + "\n");
			return;
		}
		
		// 1. n-1개를 start에서 mid로 이동
		Hanoi(n - 1, start, end, mid);
	    // 2. 1개를 start에서 end로 이동 
		sb.append(start + " " + end + "\n");
		// 3. n-1개를 mid에서 end로 이동
		Hanoi(n - 1, mid, start, end);
		
	}//Hanoi()
	
}// class Main