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

[백준 저지 링크]

11729번: 하노이 탑 이동 순서

 

재귀에 수열을 얹은 문제입니다. 

복잡한 풀이는 아니지만 수열 점화식을 만들고 재귀함수를 구현하는 아이디어를 착안해야 하는 문제입니다.

 

[정답 코드 - Java]

 

import java.io.*;
import java.io.IOException;


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));
        int N = Integer.parseInt(br.readLine());
        bw.write((int) (Math.pow(2, N) - 1) +"\n");

        Hanoi(N, 1, 2, 3);

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

    }
    public static void Hanoi(int N, int start, int mid, int to) throws IOException {
        // 원판이 1개라면?
        if (N == 1) {
            bw.write(start + " " + to + "\n");
            return;
        }
        // A -> C로 옮길 때,
        // A -> B로 N-1개를 옮긴다면?
        Hanoi(N-1, start, to, mid);
        // A -> C로 원판 1개를 옮긴다면?
        bw.write(start + " " + to + "\n");
        // B -> C로 N-1개를 옮긴다면?
        Hanoi(N-1, mid, start, to);
    }

}