<BOJ>11729번: 하노이 탑 이동 순서

문제

11729번: 하노이 탑 이동 순서

접근

• 기저 조건(base condition): n == 1 일 때, 이동 방향 출력하기
• n개의 장대를 옮기는 것은 최하단 1개와 나머지 n-1개의 한 뭉텅이로 구성된 장대 총 2개를 옮기는 것과 같다.

이를 생각해서 간단하게 재귀로 맡기자.

내 코드

import java.io.*;

public class Main {
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        sb.append((int) Math.pow(2, n) - 1).append("\n");
        solution(n, 1, 2, 3);
        System.out.println(sb);
    }

    public static void solution(int n, int start, int mid, int end) {
        if (n == 1) {
            sb.append(start).append(" ").append(end).append("\n");
            return;
        }
        solution(n-1, start, end, mid);
        sb.append(start).append(" ").append(end).append("\n");
        solution(n-1, mid, start, end);
    }
}

solution(int n, int start, int mid, int end)는 n개의 장대를 start에서 mid를 거쳐 end로 가는 것을 말한다.

따라서 재귀 조건은 다음과 같다.

n != 1인 경우를 보면,

• n-1개를 중간점으로 옮긴다.
• 1개(가장 밑)를 끝점으로 옮긴다.
• n-1개를 중간점에서 끝점으로 옮긴다.