[백준] 6092 Strange Towers of Hanoi - Dynamic Programming / Java

graycode 2024. 2. 16. 14:39

• 문제 링크

6092번: Strange Towers of Hanoi

Charlie Darkbrown sits in another one of those boring Computer Science lessons: At the moment the teacher just explains the standard Tower of Hanoi problem, which bores Charlie to death! Figure 4: The standard (three) Towers of Hanoi. The teacher points

www.acmicpc.net

• 풀이 코드

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

public class Main {

    static int[] hanoi = new int[13];

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder("1\n");

        int[] cache = new int[13];
        hanoi[1] = cache[1] = 1;

        recur(12);

        for (int i = 2; i <= 12; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= i; j++) min = Math.min(min, cache[i - j] * 2 + hanoi[j]);
            sb.append(cache[i] = min).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static int recur(int n) {
        if (n == 1) return 1;

        return hanoi[n] = recur(n - 1) * 2 + 1;
    }

}