구간 DP의 초전형. 이하, 0-indexed.

이 문제의 어려움

입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다.

접근

우선, 입력을 소트하여 n개의 요소를 $a_0, a_1, ..., a_{n-1}$로 한다.
특정 구간 $[l, r)$의 최상의 비용을 $dp[l, r)$로 나타낸다. 이때 원하는 결과는 $dp[0, n)$이다. 단, 제목보다 $dp[x, x+1) = 0$이다(즉, 어느 하나의 수를 선택하고 있을 때).
이때 $dp[l, r) = min((a_r - a_l) + dp[l+1, r), dp[l, r+1) + (a_r - a_l))$이다. 즉, 한 구간의 비용은 그보다 하나 짧은 비용에 하나 추가한 것이다. 이것을 도면에 나타내면 다음과 같이 된다.


이것을 테이블로 하면 다음과 같이 된다. (선의 합류의 min을 취해, 합류 지점의 $(a_r - a_l)$를 더한다.

구현상의 주의

파이썬은 배열에 대한 액세스가 느립니다. 이 때문에, 간단히에 쓰면(이하 실장예의 oldFunction) TLE 하는 한이 된다. 이것은 Python의 배열에 대한 액세스 속도가 관련되어있는 것 같습니다. (어느 정도 큰 배열에 대한 액세스 캐시의 폭이 좁은 것처럼 느낀다)
이 때문에, 실장예에서는 2개의 dp를 갖고, 아래로부터 계산하고 있다.


이렇게

구현 (Python3)

import sys
input = sys.stdin.readline
def do():
    n = int(input())
    dat = sorted(list(map(int, input().split())))
    dp = [0] * (n+1)
    for step in range(0, n):
        newdp = [0] * (n + 1)
        for i in range(n-step+1, n+1):
            l, r = n-step-1 , i
            newdp[i] = min(dp[i], newdp[i-1]) + (dat[r-1] - dat[l])
        dp = newdp
    print(dp[n])
do()

def oldFunction():
    n = int(input())
    dat = sorted(list(map(int, input().split())))
    dp = [0] * ( (n+1) * (n+1) )
    for width in range(2, n+1):
        for l in range(0, n - width+1):
            r = l + width
            dp[l*n + r] = (dat[r-1] - dat[l]) + min(dp[l*n + r-1], dp[l*n+n + r])
    print(dp[n])

구현(C++)

using namespace std;
int main() {
    //FASTIOpre();
    ll n; cin >> n;
    ll x; vector<ll> dat(n); REP(i, n){cin >> x; dat.at(i) = x;}
    vector<vector<ll>> table(n+1, vector<ll>(n+1, 1e18));
    sort(ALL(dat));
    REP(i, n) table.at(i).at(i+1) = 0L;
    ll r;
    FOR(width, 2, n+1){
        REP(l, n- width+1){
            r = l + width;
            table.at(l).at(r) = min(table.at(l).at(r), table.at(l).at(r-1) + (dat.at(r-1) - dat.at(l)));
            table.at(l).at(r) = min(table.at(l).at(r), (dat.at(r-1) - dat.at(l)) + table.at(l+1).at(r));
        }
    }
    cout << table.at(0).at(n) << "\n";
}