learn-algorithm/baekjoon/src/BOJ2315.java at master · cosmicb0y/learn-algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.util.Arrays;
import java.util.Scanner;

public class BOJ2315 {
    static int n;
    static int m;
    static int[][] light;
    static int[][][] DP;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        light = new int[n + 1][3];
        DP = new int[n + 1][n + 1][2];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                Arrays.fill(DP[i][j], -1);
            }
        }


        for (int i = 1; i <= n; i ++) {
            light[i][0] = sc.nextInt();
            light[i][1] = sc.nextInt();
            light[i][2] = light[i - 1][2] + light[i][1];
        }

        System.out.println(minWaste(m, m, 0));

    }

    private static int minWaste(int left, int right, int where) {
        if (left == 1 && right == n) {
            return 0;
        }

        if (DP[left][right][where] !=  -1) {
            return DP[left][right][where];
        }

        int min = Integer.MAX_VALUE;

        int now;
        if (where == 0) {
            now = left;
        }
        else {
            now = right;
        }

        if (left - 1 >= 1) {
            min = Math.min(min, minWaste(left - 1, right, 0) + (light[now][0] - light[left - 1][0]) * (light[n][2] - light[right][2] + light[left - 1][2]));
        }

        if (right + 1 <= n) {
            min = Math.min(min, minWaste(left, right + 1, 1) + (light[right + 1][0]  - light[now][0]) * (light[n][2] - light[right][2] + light[left - 1][2]));
        }

        DP[left][right][where] = min;

        return min;
    }
}