문제해설

문제에 나이차이에 대한 언급이 있는데 기준이 주어지지 않아서 이해하는데 꽤나 시간이 걸렸다. (분명히 나이차이를 이해 못해서 못 푼 사람이 있을것이다.)
해석해보자면 조를 짤 때 한 조에 몇명이든, 조를 몇개 짜든 상관 없지만 어떤 A와 B가 C조일 경우 A와 B 사이의 나이를 가지는 사람들은 모두 C조이어야 한다는 뜻이다.
즉, 입력값이 나이순으로 주어지기 때문에 어떤 입력값 A, B가 한 조일 경우 그 사이 값들은 모두 A, B와 같은 조이어야 한다.

DP

헷갈리는 부분을 해결하고 나니 문제 자체의 난이도는 쉬운 편이었고, DP를 사용해야한다.
한조에 한명만 있을 경우 값이 0 이므로 DP[1] = 0 이고 두명이 있을경우 높은 점수에서 낮은 점수를 뺀 값이 저장된다.
DP[i] 같은 경우 i번째 학생 혼자 조를 한 값과 DP[i - 1]을 더하는 경우부터 i번째와 i - 1번째 학생 둘이서 조를 이룬 값과 DP[i - 2]의 값을 더하는 순서로 모든 경우를 탐색하면된다.

7번째를 예를들어 설명하자면, 7번 학생 혼자 조를 이룬값 + DP[6], 6번과 7번 학생이 조를 이룬값 + DP[5], 5번과 6번과 7번이 조를 이룬값 + DP[4], ... , 1번부터 7번까지 한 조를 이룬값 중 가장 큰 값이 DP[7]의 값이 된다.

시간복잡도

시간복잡도는 i번째에서 i번 만큼의 탐색이 이루어지므로 1 + 2 + 3 + ... + N - 1 + N 이고
이 값은 N(N + 1) / 2 의 값과 같으므로 시간복잡도는 O(N²)이다. (N <= 10,000)

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        int N, score[], dp[];
        N = Integer.parseInt(br.readLine());
        score = new int[N + 1];
        dp = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            score[i] = Integer.parseInt(st.nextToken());
        }

        dp[2] = Math.abs(score[1] - score[2]);
        for (int i = 3; i <= N; i++) {
            dp[i] = dp[i - 1];
            for (int j = 2; j <= i; j++) {
                dp[i] = Integer.max(dp[i], dp[i - j] + Math.abs(score[i] - score[i - j + 1]));
            }
        }

        bw.write(String.valueOf(dp[N]));
        bw.flush();
        bw.close();
    }
}