백준 : 2262

그리디로도 풀 수 있다는데 dp로 풀었다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static int N;
    static int dp[][];
    static int arr[];
    static final int INF = 987654321;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        dp = new int[N][N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        System.out.println(dfs(0, N - 1));
    }
 
    public static int dfs(int l, int r) {
        if (dp[l][r] != 0) {
            return dp[l][r];
        }
 
        if (l == r)
            return 0;
 
        int minValue = INF;
 
        for (int i = l; i < r; i++) {
            int left = dfs(l, i);
            int right = dfs(i + 1, r);
            int m1 = INF;
            int m2 = INF;
            int j;
            for (j = l; j <= i; j++) {
                m1 = Math.min(m1, arr[j]);
            }
            for (; j <= r; j++) {
                m2 = Math.min(m2, arr[j]);
            }
            minValue = Math.min(minValue, left + right + Math.abs(m1 - m2));
        }
 
        return dp[l][r] = minValue;
    }
}

 

그리디 아이디어는 등수가 1등에 가까울수록 나중에 경기를 치루어야한다.