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

문제보기

11729번: 하노이 탑 이동 순서

대부분의 사람들이 재귀를 처음 배울 때 보는 문제인듯 싶습니다.

저는 처음 배울 때 치곤 어렵다고 생각하지만 ㅠㅠ

그래서 원리는 여기저기서 듣다 보니 기억에 박혀있는 것 같습니다.

그래서 하노이에 대한 설명은 따로 안하고

이 문제만의 특이한 점인 첫 번째 줄에 출력하는 옮긴 횟수에 대해서만 언급하겠습니다.

옮긴 횟수를 나열해보면

1개	2개	3개	4개	5개
1회	3회	7회	15회	31회

저는 이렇게 적어 본 후 2^n -1 이란게 보였지만 원리는 모르겠어서

찾아보면서 적었습니다.

이렇게 되는 이유는 원반의 개수가 늘어날 때마다 ( n -> n+1 )

횟수를 기준으로

1번에서 2번까지 n개의 원반의 이동이 일어나고(hanoi(n)) n+1번째 원반을 3번으로 옮기고(1)

다시 n개의 원반을 이동하게 됩니다. (hanoi(n)) 이걸 정리해보면

hanoi(n+1) = hanoi(n)*2 + 1 이 되는데 이건 등비수열의 점화식이 됩니다.

해당 점화식을 풀어보면 hanoi(n) = 2^n - 1이 나오게 됩니다.

import java.util.*;

public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.close();
        hanoi(N, 1, 2, 3);
        System.out.println((int)Math.pow(2, N)-1);
        System.out.println(sb);
    }    
    public static void hanoi(int n, int from, int by, int to) {
        if(n == 1) {
            sb.append(from + " " + to + "\n");
            return ;
        }
        hanoi(n-1, from, to, by);
        sb.append(from + " " + to + "\n");
        hanoi(n-1, by, from, to);    
    }
}