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

 

재귀함수를 처음 배울때 피보나치 수열과 함께 단골로 등장하는 문제이다.

 

하노이 탑 풀이 방법을 까먹어서 인터넷을 참고했다.

똑똑한 사람이 너무도 많아 아무데나 검색만 해도 자세한 풀이가 나온다.

 

public class Main {
    
    static int cnt = 0;
    static StringBuilder sb = new StringBuilder();
    
    public static void move(int from, int to) {
        cnt++;
        sb.append(from + " " + to + "\n");
    }
    
    public static void hanoi(int n, int from, int by, int to) {
        if(n == 1)
            move(from, to);
        else {
            hanoi(n-1, from, to, by);
            move(from, to);
            hanoi(n-1, by, from, to);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int k = sc.nextInt();
        
        hanoi(k, 1, 2, 3);
        
        System.out.println(cnt);
        System.out.println(sb.toString());
    }
}