https://codeforces.com/contest/1509/problem/C
시간 1초, 메모리 256MB
input :
- n (1 ≤ n ≤ 2000)
- s1 , s2, ..., sn (1 ≤ si ≤ 109)
output :
- Print a single integer — the minimum possible value of d1 + d2 + ... + dn after choosing the order of the members.
가능한 최솟값을 출력하시오.
조건 :
-
The discrepancy di of the i-th stage is the difference between the maximum and the minimum running speed among the first
imembers who ran.
i번째 차례에서의 di는 i명의 멤버가 달릴 때 최고, 최저 속도의 차를 의미합니다. -
Formally, if ai denotes the speed of the i-th member who participated in the race, then di = max(a1, a2, …, ai) − min(a1, a2, …, ai).
일반적으로, ai는 i번째 멤버의 속도를 나타냅니다.
본인이 이루고 있는 부분배열의 최대, 최소값의 차이를 누적해 가는 것이고 이 값을 가장 작게 만들어야 한다.
경우
가장 큰 값이나 작은 값의 경우 제일 마지막에 들어가야 한다.
이런 값들은 언제나 절대값의 차이가 아주 크기 때문에 최소값보다 커지게 된다.
그렇다면 동일한 숫자를 가지고 있는 경우는? 이도 동일한데 일단은 생각해 줄 필요는 없다.
가장 중요한 것은 가장 큰, 작은 값은 마지막에 들어가는 것이다.
시작점
그렇게 되면 중간에서 부터 시작을 하는데 만약 현재 위치가 l ~ r까지라고 생각을 해보자.
l - 1 ~ r + 1로 두 개의 원소를 추가해서 넣고 싶을 때 내가 해야 하는 것은 무엇인가?
l - 1을 먼저 넣은 배열 혹은 r + 1을 먼저 넣은 배열을 만든 이후에 넘어갈 수 있다. 그렇다면 우리는 둘 중 절대값이 더 작을 수 있는 놈을 먼저 해야 한다.
이러한 사고과정이 발생할 때 우리는 DP를 생각해야 한다.
위의 사고 과정을 수학적으로 생각한다면
dp[l - 1][r + 1] = data[r + 1] - data[l - 1] + min(dp[l - 1][r], dp[l][r + 1])처럼 만들 수 있다.
물론 l + 1 ~ r - 1에서 l ~ r을 만드는 것으로 생각해도 된다.
그리고 앞의 data의 경우 입력 받은 배열을 오름차순으로 정렬 한다면
언제나 r에 있는 값이 max가 되고 l에 있는 값은 min이 되기 때문에 지정해서 계산을 할 수 있다.
구현
식까지는 이해가 쉬웠다.
구현을 어떻게 하느냐가 예상외의 복병이었다.
결국 내가 원하는 답은 dp[0][n - 1]의 값을 찾는 것인데.
이를 보면 0 ~ n - 1까지의 값을 구할 때 필요한 것
0 ~ n - 2, 1 ~ n - 1
0 ~ n - 3, 1 ~ n - 2, 1 ~ n - 3, 2 ~ n - 1 ....
처럼 모든 경우를 다 확인 해야 한다.
모든 경우를 확인할 거면 반복문 2개로 충분하고 마지막에 0 ~ n - 1에 누적되어야 하기 때문에 인덱스를 뒤에서 부터 n - 2 ~ n - 1, n - 3 ~ n - 1, ... 처럼 뒤에서 부터 모든 부분 배열을 확인하도록 하자.
이 경우 i가 점점 작아지면서 j는 어차피 n까지 올라가기 때문에 모든 경우를 확인하게 되고
값은 계속 누적되어 원하는 값을 얻을 수 있다.
import sys
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
data.sort()
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
dp[i][j] = data[j] - data[i] + min(dp[i + 1][j], dp[i][j - 1])
print(dp[0][-1])
