[백준/Java] 1914 - 하노이 탑

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

문제

---

풀이

재귀를 사용하여 해결하였다

hanoi(옮길 원판 개수, 첫번째 장대, 두번째 장대, 세번째 장대) {
    if 옮길 원반이 0개면 {
        return;
    }

    첫번째 장대에서 가장 아랫칸을 제외한 나머지 원반들을 두번째 장대로 옮김
    가장 아랫칸 원판을 세번째 장대로 옮김
    나머지 원반들을 두번째 장대에서 세번째 장대로 옮김
}

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Ureca {
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
//        StringBuilder sb = new StringBuilder();
        sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        // N이 20보다 클 경우에는 공식을 사용하여 계산
        // 2^N - 1
        // N = 100 이면 2^100을 계산해야 하기 때문에 BigInteger를 사용
        BigInteger num = new BigInteger("2");
        sb.append(num.pow(N).subtract(new BigInteger("1")));

        // N이 20 이하일 때만 과정 출력
        if (N <= 20) {
            sb.append("\n");
            hanoi(N, 1, 2, 3);
        }

        System.out.println(sb);

        br.close();
    }

    static void hanoi(int N, int from, int tmp, int to) {
        // 옮길 원반이 0개면 return
        if (N == 0) {
            return;
        }

        // 첫번째 장대에서 가장 아랫칸을 제외한 나머지 원반들을 두번째 장대로 옮김
        hanoi(N - 1, from, to, tmp);
        sb.append(from).append(" ").append(to).append("\n");
        // 나머지 원반들을 두번째 장대에서 세번째 장대로 옮김
        hanoi(N - 1, tmp, from, to);
    }
}

결과