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

 

 

문제

하노이의 탑에 있는 N개의 원판을 '1'에서 '3'으로 이동시킬 때, 탑의 이동 순서를 출력하는 문제이다.

하노이의 탑 풀이는 공식처럼 외워서 사용하는 편이 편한 것 같다.

핵심적인 논리는 N개의 원판을 '1'에서 '3'으로 이동시키기 위해

우선 N-1개를 '1'에서 '2'(도움닫이 공간)으로 이동시킨 후, 마지막 1개의 원판을 '3'으로 이동시키는 것이다.

이동시킨 후엔 '2'(도움닫이 공간)으로 이동시킨 원판을 다시 '3'으로 이동하는 방식으로 진행한다.

그림을 그려가며 이해하는 것이 좋다.

 

 

 

풀이

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

public class Main {
    static StringBuilder sb;

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

        sb = new StringBuilder();
        sb.append(String.valueOf((int) Math.pow(2, N) - 1)).append("\n");

        recursion(N, 1, 2, 3);
        System.out.println(sb);
    }

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

        recursion(disk - 1, start, end, mid);
        sb.append(start).append(" ").append(end).append("\n");
        recursion(disk - 1, mid, start, end);
    }
}

 

 

채점결과