[Baekjoon] 하노이 탑 이동 순서

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

설명 : 알고리즘 강의에서 재귀함수에 대한 부분에서 항상 언급되는 하노이타워 문제이다.

N개의 원판을 A에서 C로 옮길 때, 

1. N-1개의 원판을 A에서 B로 옮긴후,

2. A에 남아있는 가장 큰 원반을 C로 옮긴다. 

3. 다시 N-1개의 원판을 B에서 A로 옮기면 된다.

코드 :

 
package feb12.hanoi;
 
import java.util.Scanner;
 
 
public class Main {
    
    
    public void hanoi(int i, int start, int mid, int end){
    
        if(i == 1){
            System.out.println(start + " " + end);
        }
        else {
            hanoi(i - 1, start, end, mid);
            System.out.println(start + " " + end);
            hanoi(i - 1, mid, start, end);
        }
        
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        int N;
        Scanner sc = new Scanner(System.in);
        Main m = new Main();
        N = sc.nextInt();
        
        System.out.println((int)Math.pow(2, N) - 1);
        m.hanoi(N, 1, 2, 3);
        
        
    }
 
}