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

풀이

이전에 학교를 다니면서 풀어보았던 문제이기에 덤벼 들었다. 위의 문제는 일반적인 점화식을 찾는것이 중요하면 규칙을 찾는것 또한 중요하다. 재귀함수의 규칙이라고 해서 어려운것이 아니다 그냥 가장 작은 문제로 줄여가면서 규칙을 찾아야 한다. 예전에 보았던 문제라도 다시 보고 또 봐야겠다.

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), "");

        int N = Integer.parseInt(st.nextToken());
        bw.write((int) Math.pow(2, N) - 1 + "\n");

        Hanoi(N, 1, 2, 3);

        bw.flush();
        bw.close();

    }

    public static void Hanoi(int n, int start, int mid, int to) throws IOException{

        //하나 일때 이동
        if (n == 1) {
            bw.write(start + " " + to + "\n");
            return;
        }

        //step 1  n-1 A->B이동
        Hanoi(n-1, start, to, mid);

        //step 2 1개이동 A->C이동
        bw.write(start + " " + to + "\n");

        //step 3 n-1 이동 B->C이동
        Hanoi(n-1, mid, start, to);
    }
}