21.08.10 기록

백준 알고리즘 11729 풀이

🎆해설(메모리 101MB, 시간 536ms로 통과)

-손코딩 후 타이핑으로 풀이해봤지만 도저히 풀지 못하겠어서 해설을 봤다.
-하노이 탑 공식은 수열로 유도할 수 있다.

n개의 원판을 이동시키기 위한 이동 횟수를 $a_n$이라고 할 때, n개의 원판을 옮기려면 그 위쪽에 있는 ①(n-1)개의 원판을 모두 다른 막대로 옮긴 후, ②맨 아래 원판을 빈 막대로 옮긴 다음에 ③그 위에 (n-1)개의 원판을 옮겨놓아야한다.

• 수식으로 표현하면 ①은 $a_{n-1}$, ②는 1, ③은 $a_{n-1}$로 아래와 같다.
• $a_n = a_{n-1} + 1 + a_{n-1} = 2 × a_{n-1} + 1$
• 위 수식을 귀납적으로 정리하면 일반항은 $a_n = 2^n-1$이다. (상세 내용 해설 링크 참조)

-공식을 사용한 코드는 아래와 같다.

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

public class B11729 {
    public static StringBuilder sb = new StringBuilder();

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

        sb.append((int) (Math.pow(2, N) - 1)).append("\n");
        hanoi(N, 1, 2, 3);
        System.out.println(sb);

    }

    //start: 출발지, mid: 옮기기 위해 이동하는 장소, end: 목적지
    public static void hanoi(int N, int start, int mid, int end) {
        if(N == 1) {
            sb.append(start + " " + end + "\n");
            return;
        }

        //1. N-1개를 A에서 B로 이동
        hanoi(N-1, start, end, mid);

        //2. 1개를 A에서 C로 이동
        sb.append(start + " " + end + "\n");

        //3. N-1개를 B에서 C로 이동
        hanoi(N-1, mid, start, end);
    }
}