BOJ 11729 - 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

---

 

n개의 원판이 시작점에서 경유지를 거쳐 도착점까지 가는 과정을 F(n) 이라고 해보자.

그리고 세 장대를 각각 A, B, C라고 하자.

A 맨 밑에 있는 원판을 C로 옮기기 위해서는 다음과 같은 과정을 거쳐야 한다.

 

1. A에 맨 밑에 있는 원판을 제외한 원판 (n-1)을 C를 경유하여 B로 옮긴다. -> F(n-1)

2. A에 있는 원판을 C로 옮긴다. -> 1

3. B에 있는 원판을 A를 경유하여 C로 옮긴다. -> F(n-1)

 

따라서 F(n) = 2 * F(n-1) + 1 이라는 점화식이 등장한다.

 

이 점화식을 바탕으로 재귀를 돌리고 n 값이 가장 작은 단위(1)가 될 때 출력해주면 구현이 완성된다.

 

 

 

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

public class Main {
    static StringBuilder SB = new StringBuilder();
    static int COUNT = 0;

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

        hanoi(number, 1, 2, 3);

        System.out.println(COUNT);
        System.out.println(SB);
        br.close();
    }

    public static void move(int start, int end) {
        COUNT++;
        SB.append(start + " " + end + "\n");
    }

    public static void hanoi(int number, int start, int via, int end) {
        if (number == 1) {
            move(start, end);

            return;
        }

        hanoi(number - 1, start, end, via);
        move(start, end);
        hanoi(number - 1, via, start, end);
    }
}