백준 1914번 하노이 탑[골드 5][Java]

1. 개요

 안녕하세요. 오늘 문제의 유형은 재귀입니다. 아주 유명한 웰노운 알고리즘인 하노이타워를 다루는 문제입니다. 그런데 문제가 있습니다. 입력으로 주어지는 원판의 개수가 최대 100개까지 주어지는데요. 문제는 하노이타워를 첫 번째 장대에서 다른 장대로 이동시키는데 필요한 최소 이동 횟수를 출력하도록 되어있습니다. 하노이타워의 시간복잡도는 원판의 개수를 n이라고 했을 때, O(2^n - 1)입니다. 즉 pow(2, 100) - 1이라는 매우 큰 수를 출력해야합니다. 이는 8 byte 변수로도 담을 수 없는 큰 수라 C++로 풀이를 시도하면 큰 수 구현을 직접해야하므로 번거롭습니다.

 

2. 문제 풀이

 저는 큰 수를 계산하고 출력하기 위해 C++ 대신 자바를 사용하여 풀이했습니다. 자바에서 제공하는 BigInteger를 사용하여 이동 횟수를 쉽게 계산했습니다. 이동 경로는 하노이타워 알고리즘을 그대로 가져와 구현하시면 됩니다.

 

3. 코드

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {

    private static StringBuilder sb = new StringBuilder();
    private static int N;

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

        N = Integer.parseInt(br.readLine());        

        BigInteger cnt = new BigInteger("2");
        BigInteger offset = new BigInteger("-1");
        sb.append(cnt.pow(N).add(offset).toString()).append("\n");

        if(N <= 20) {
            hanoi_tower(1, 2, 3, N);
        }

        System.out.println(sb.toString());
    }

    private static void hanoi_tower(int A, int B, int C, int N) {
        if(N == 1) {
            sb.append(A).append(" ").append(C).append("\n");
            return;
        }
        hanoi_tower(A, C, B, N - 1);
        sb.append(A).append(" ").append(C).append("\n");
        hanoi_tower(B, A, C, N - 1);
    }
}

 

4. 제출 결과