문제

아이디어

유명한 하노이 탑 문제다. 우선 높이가 N의 원판을 옮기는 방법에 대해서 생각해보자.

1. N = 1이라면 목표 장대로 옮긴다.
2. N != 1이라면 가장 큰 원판을 제외한 N-1개의 원판을 목표하지 않는 장대로 옮긴다.
3. 가장 큰 원판을 목표 장대로 옮긴다.
4. 2번에서 옮긴 N-1개의 원판을 목표 장대로 옮긴다.

문제는 옮긴 횟수와 수행 과정을 출력하는 두 가지의 소문제로 나뉜다.

위의 알고리즘에 따라 N층의 하노이탑은 N^2-1 번 원판을 옮긴다는걸 쉽게 도출해낼 수 있지만, N은 100 이하의 자연수로 long의 범위를 벗어난다.

따라서 Java에서 제공하는 BigInteger를 이용하여 옮긴 횟수를 계산하고, 수행 과정은 재귀 호출을 통해 구할 수 있겠다.

소스코드

import java.io.*;
import java.math.BigInteger;

public class Main {
    static int N;
    static StringBuilder ans;

    static void hanoi(int from, int to, int size) {
        if (size == 0) return;
        hanoi(from, 6 - from - to, size - 1);
        ans.append(from).append(' ').append(to).append('\n');
        hanoi(6 - from - to, to, size - 1);
    }

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

        ans.append(BigInteger.valueOf(2).pow(N).subtract(BigInteger.ONE)).append('\n');

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

        System.out.print(ans);
    }
}

채점결과

서버 상태가 좋았는지 Java 풀이 중 1등을 기록했다. 야호!