algorithms 백준 (BOJ)

(BOJ)백준 11066 (baekjoon 11066)

2019.11.15 ·

(BOJ)백준 11066 - 11066번: 파일 합치기

11066번: 파일 합치기

[BOJ] 백준 (11066)

백준 11066 - 11066번: 파일 합치기

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

코드

import java.io.*;
import java.util.Arrays;

public class B11066 {
    final static int INF = 987654321;
    static int t, k, a[] = new int[501], dp[][] = new int[501][501], prefix[] = new int[501];
    static String[] ins;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        t = Integer.parseInt(br.readLine());
        while (t-- != 0) {
            Arrays.fill(a, 0);
            k = Integer.parseInt(br.readLine());
            ins = br.readLine().split(" ");
            for (int i = 0; i < k; i++) {
                a[i + 1] = Integer.parseInt(ins[i]);
                prefix[i + 1] = (i == 0) ? a[i + 1] : a[i + 1] + prefix[i];
            }
            for (int i = 0; i <= k; i++) Arrays.fill(dp[i], -1);
            bw.write(dp(1, k) + "\n");
            bw.flush();
        }
        bw.close();

    }

    public static int dp(int l, int r) {
        if (l == r) return 0;
        if (r - l == 1) return a[l] + a[r];
        if (dp[l][r] != -1) return dp[l][r];
        dp[l][r] = INF;
        for (int i = l; i < r; i++) {
            dp[l][r] = Math.min(dp[l][r], prefix[r] - prefix[l - 1] + dp(l, i) + dp(i + 1, r));
        }

        return dp[l][r];
    }





}

설명