2229

나이순으로 정렬이 이미 되었으니 해야 할 일은 여기서 연속된 배열을 어떻게 여러개로 나눠서 최대의 점수를 내는 조를 만드느냐이다.

(문제가 나이 정렬을 해주지 않고 냈으면 더 어려울 뻔 했는데 친절하게 나이 정렬을 해준 뒤에 문제를 풀라고 했다)

위 문제는 DP로 풀 수 있다. 먼저 다음과 같은 배열을 선언한다

dp[FROM][TO] : FROM학생부터 TO학생까지 조를 짤 때의 최대의 점수가 나오는 경우

목표는 FROM, TO까지 무조건 최대의 점수를 가지는 것이며 어떻게 분할 되는지는 상관하지 않는다

FROM에서 TO까지의 범위를 차근차근 늘려서 1번 학생부터 N번 학생가지 포함되는 경우까지 만들어준다.

 
#include<cstdio>

#define MAXN 1000

#define MAX(A, B) ((A) > (B) ? (A) : (B))
#define MIN(A, B) ((A) < (B) ? (A) : (B))
#define INF 10005


int dp[MAXN + 5][MAXN + 5];

int arr[MAXN + 5];

int main() {
	int N, i, j, len;

	int _min, _max;

	freopen("input.txt", "r", stdin);
	scanf("%d", &N);

	for (i = 0; i < N; i++)
		scanf("%d", &arr[i]);

	for (len = 0; len < N; len++) {
		for (i = 0; i + len < N; i++) {
			_min = INF, _max = 0;

			for (j = i; j <= i + len; j++) {
				_min = MIN(_min, arr[j]);
				_max = MAX(_max, arr[j]);

				dp[i][i + len] = MAX(dp[i][j] + dp[j + 1][i + len], dp[i][i+len]);
			}

			dp[i][i + len] = MAX(_max - _min, dp[i][i + len]);
		}
	}

	printf("%d\n", dp[0][N - 1]);

	return 0;
}

하지만 위 방법은 O(N^3)이다. 2초 제한시간에 아슬아슬하게 통과했지만(772ms) 원칙상으로는 통과해선 안된다.

다른 사람들의 코드를 봤는데 상위랭크는 대부분 O(N^2)로 풀었다.

나와 푼 방식의 개념은 기본적으로 비슷하나 이분들은 FROM은 어차피 1이 될 것이기 때문에 이 경우를 무시하고 dp[TO]만 가지고 풀었다.

새로운 dp[TO]를 만들기 위해 TO' < TO에서 dp[TO'] + (TO'+1 부터 TO 까지 조를 짤 경우)에 대한 최대값을 계속 업데이트 해줬다.

내 방법보다 한 번 더 추상화해서 문제에 접근한 방식이다.

정말 고수는 다르구나 하는 생각이 들었다.

 
    dp[1] = fabs(arr[1]-arr[0]);
    for(int i=2; i<n; i++)
    {
        maxnum=minnum=arr[i];
        for(int j=i; j>0; j--)
        {
            maxnum = max(maxnum, arr[j]);
            minnum = min(minnum, arr[j]);
            dp[i] = max(dp[i], maxnum-minnum+dp[j-1]);
        }
    }
    printf("%d", dp[n-1]);