백준|11729번|하노이 탑 이동 순서

문제설명
하노이탑의 원판 개수를 입력받고 모든 원판을 1번에서 3번으로 옮기는데 필요한 최소한의 연산 순서와 이동순서를 출력하는 문제입니다.

작동 순서
1. 원판의 개수 N을 입력받습니다.
2. 하노이탑의 이동순서는 옮기려는 원판 바로 위의 원판을 옮긴뒤 옮기려는 원판을 목표위치로 옮긴뒤 자신 바로위에 있던 원판을 목표위치로 옮기는 것으로 분해가 가능합니다.
3. 2번의 연산을 각 원판마다 수행하면 결국 N번째 원판을 옮기는 방식은 N-1의 원판부터 1번 원판까지 2번 연산을 수행하게 됩니다.
4. 모든 연산을 완료하면 이동횟수와 이동순서를 출력합니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 백준_11729번_하노이탑이동순서 {
    static StringBuilder sb = new StringBuilder();
    static int count=0;
    static void hanoi(int n, int start,int through, int to){
        if(n==1) {
            count++;
            sb.append(start+" "+to+"\n");
        }
        else{
            hanoi(n-1, start, to, through);
            hanoi(1, start, through, to);
            hanoi(n-1, through, start, to);
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        hanoi(N, 1, 2,3);
        System.out.println(count);
        System.out.print(sb);
    }
}

후기
재귀 문제를 풀어보니 생각보다 복잡하네요. 피보나치나 팩토리얼등보다는 확실히 훨씬 어려운 것 같습니다. 그래도 다양한 유형을 접해보면서 실력을 키워야 할 것 같습니다.