백준4008 특공대

작성일 | In

문제 링크

  • https://www.acmicpc.net/problem/4008

문제 출처

  • 2010 APIO 1번

사용 알고리즘

  • DP
  • Convex Hull Trick

시간복잡도

  • O(n3)
  • O(n2)
  • O(n log n)
  • O(n)

풀이

APIO(Asia-Pacific Informatics Olympiad, 아시아-태평양 정보올림피아드)2010에 1번 문제로 나온 특공대(Commando)라는 문제입니다.

문제를 요약하자면,

  • 사람 수 N과 이차함수의 계수 a, b, c가 주어진 후, 각각의 사람에 대한 능력치 Xi가 주어진다.
  • 연속된 사람들끼리 분할해서 각 구간의 합을 함수에 이차함수에 대입했을 때의 최대값을 출력한다. 정도가 됩니다.

일단 dp배열을 정의하자면, dp[n]은 n번 사람까지만 고려했을 때의 답을 저장하는 배열입니다.
s배열은 Xi의 누적합을 저장한 배열입니다.
일단, dp[0]을 0으로 정합니다.

점화식을 세워보면,
1 <= i < n 일 때, dp[n] = max{ (i까지의 최적해) + (i+1부터 n까지의 결과) }
라고 할 수 있습니다.

수식으로 바꾸겠습니다.

전개를 하면 다음과 같이 변합니다.

설명을 쉽게 하기 위해 순서를 약간 바꾸도록 하겠습니다.

위에서
1 <= i < n 일 때, dp[n] = max{ (i까지의 최적해) + (i+1부터 n까지의 결과) }
라고 정의했기 때문에 max는 i의 변화를 주시하고 있습니다. 즉, i와 상관 없는 항들은 max 밖으로 빼낼 수 있습니다.

그러므로 식은 다음과 같이 바꿀 수 있습니다.

위 식에서 max 안에 있는 s[n]을 x로 치환해보겠습니다.

그러면 max 안에 있는 식은 기울기가 -2as[i]이고, 절편이 as[i]^2 - bs[i] + dp[i]인 일차함수가 됩니다.
또한, dp[n]에서는 n이 고정되어 있으므로 s[n]도 고정이기 때문에 as[n]^2 + bs[n] + c은 상수 취급할 수 있습니다.

위 식을 조금 더 보기 편하게 하기 위해 k와 m을 다음과 같이 정의하겠습니다.

  • k[i] = -2as[i] - 기울기입니다.
  • m[i] = as[i]^2 - bs[i] + dp[i] - 절편입니다.

그러면, dp식은 더욱 보기 편해집니다.

i를 1부터 n까지 돌리고, j를 1부터 i-1까지 돌리면 O(n2)에 답을 구할 수 있습니다.
만약 누적합 배열을 안쓴다면 O(n3)이 나오겠죠.
하지만, n이 최대 1,000,000이기 때문에 시간복잡도를 줄여야 합니다.
아무리 봐도 이 식은 n^2으로만 해결할 수 있어 보입니다. 하지만 Convex Hull Trick을 쓰면 O(n)만에 답을 구할 수 있습니다.

이제부터 Convex Hull Trick을 사용하여 이 문제를 해결해보겠습니다.

먼저, max 안에 들어가는 일차 함수의 기울기는
-2as[i]
입니다.

  1. -2는 음수이고, a는 -5이상 -1이하로 주어지기 때문에 a 또한 음수입니다.
  2. 각 사람의 능력치는 양수이고, s배열은 능력치의 누적합이므로 i가 커질 수록 s[i]는 항상 증가합니다.

위 두 가지 근거로 인해 기울기는 항상 양수이며, i가 커질수록 기울기도 커진다는 사실을 알 수 있습니다.

빨간색, 초록색, 파란색, 회색 순서대로 함수가 주어진다면 다음과 같이 그래프가 그려집니다.

이 문제에서는 최대값을 구해야 하기 때문에 분홍색으로 전체 함수들의 최대값도 표시해주었습니다.
이 그래프에서 초록색 그래프, 즉 두 번째로 들어온 그래프는 생략을 해도 정답에 영향을 끼치지 않습니다.
이렇게 필요 없는 그래프를 제거해주면서 최적화를 할 수 있습니다. 줄이는 방법을 알아봅시다.


빨간색(이하 1번), 초록색(이하 2번) 함수만 있는 상태에 파란색(이하 3번) 함수가 추가되었다고 가정합시다.

1번, 3번의 교점과 1번, 2번의 교점의 위치 관계를 비교해보면 1, 3번의 교점이 더 앞에 있습니다.

  1. 일단, 1, 2번 교점의 앞 부분에서는 2번 함수가 더 작기 때문에 어떠한 영향도 끼치지 못합니다.
  2. 그리고 1, 3번 교점의 뒤 부분에서는 3번 함수가 2번 함수보다 더 크기 때문에 해당 공간에서도 2번 함수는 어떠한 영향도 끼지치 못합니다. 위 두 가지 조건의 합집합은 모든 구간이 됩니다. 그러므로 2번 함수는 모든 구간에서 영향을 끼치지 못하는 함수이기 때문에 생략 가능합니다.

이러한 과정을 거쳐 필요 없는 함수를 생략하면 다음과 같은 꼴의 그래프가 남게 됩니다. (위에 올린 그래프와 다른 그래프입니다.)

보기 좋게하기 위해 필요 없는 부분을 지우면 다음과 같이 됩니다.

이 그래프의 x값에 s[n]을 대입하면 dp[n]이 나오게 됩니다.
최종 결과가 볼록 다각형, 즉 Convex Hull의 일부같이 생겨서 이 기법을 Convex Hull Trick이라 부릅니다.

이 문제는 i가 증가하면 항상 함수값이 증가하기 때문에 최소, 최대값을 찾기가 쉽지만, 다른 문제에서는 최종 함수가 convex hull꼴이라도 i가 작아질수록 항상 함수값이 작아지지 않는 경우도 있습니다. 그런 경우에는 binary search를 이용해야 하기 때문에 O(n log n)이 나오고, 이 문제는 binary search가 필요 없기 때문에 O(n)이 나옵니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vll;

int n, a, b, c;
const int size = 1000010;
vll v(size), s(size), dp(size), xpos(size), stk(size);
int scnt;

inline ll func(ll x){
	return (ll)a*x*x + (ll)b*x + c;
}

inline ll k(ll i){
	return -2*a*s[i];
}

inline ll m(ll i){
	return a*s[i]*s[i] - b*s[i] + dp[i];
}

double getCross(int p, int q){ //교점
	ll k1 = k(p), m1 = m(p);
	ll k2 = k(q), m2 = m(q);
	return (double)(m1-m2) / (k2-k1);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> a >> b >> c;
	for(int i=1; i<=n; i++) cin >> v[i], s[i] = s[i-1] + v[i];
	int pt = 1;
	for(int i=1; i<=n; i++){
		dp[i] = func(s[i]);
		if(scnt){
			while(pt<scnt && xpos[pt+1]<s[i]) pt++; //점화식의 우항이 최대인 위치 구함
			int j = stk[pt];
			dp[i] = max(dp[i], dp[j] + func(s[i]-s[j]));

			while(scnt>1 && xpos[scnt]>getCross(stk[scnt], i)) --scnt;
			stk[++scnt] = i;
			xpos[scnt] = getCross(stk[scnt-1], i);
			if(pt > scnt) pt = scnt;
		}else{
			stk[++scnt] = i;
			xpos[scnt] = -1e9;
		}
	}
	cout << dp[n] << endl;
	return 0;
}