백준 11729번 하노이탑 이동순서(Java)

유명한 문제. 복잡하게 생각할 수록 어려운 문제다. 장대의 개수가 3개보다 많을시 난이도역시 오르는 문제. 하지만 3개여서 매우 쉽다. 분할정복을 사용해서 풀면 매우 간단하다.

가장 큰 원판을 3번째 장대로 옮기는걸 n번 반복하면 된다. 즉 n번째의 원판을 이동시키려면 n-1번째까지의 원판을 모두 2번째 장대로 옮겨야 된다. 그 후 2번째 장대로 옮겨놓은 판을 다시 3번째 장대로 옮기기만 하면 끝. 

import java.util.Scanner;

public class Main {

    static void hanoi(int n,int start,int middle,int to){
        if(n==1) {
            System.out.println(start + " " + to);
            return;
        }
        hanoi(n-1,start,to,middle);
        System.out.println(start+" "+to);
        hanoi(n-1,middle,start,to);
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        System.out.println((int)(Math.pow(2,n))-1);
        hanoi(n,1,2,3);
    }
}