백준10714 케이크 자르기2

작성일 | In

문제 링크

  • http://icpc.me/10714

문제 출처

  • 2015 JOI 2번

사용 알고리즘

  • DP

시간복잡도

  • O(N2)

풀이

이 문제처럼 DP로 풀 수 있습니다.

i번째 조각을 기준으로 i-1번째를 왼쪽, i+1번째를 오른쪽이라고 합시다.
현재 상황까지 가져간 가장 왼쪽 위치는 l, 가장 오른쪽 위치를 r이라고 할 때 최댓값을 dp[l][r]로 정의합시다.

ioi의 차례에서는 (l-1)번째와 (r+1)번째 중에서 더 큰 값을 가져가면 됩니다.
joi의 차례에서는 (l-1)번째와 (r+1)번째를 가져갔을 때, 최종적으로 더 큰 결과를 갖게 되는 쪽을 택하면 됩니다.

엄밀하게 말하면, (l-1)과 (r+1)번째가 아닌 (l-1+n)%n과 (r+1)%n번째를 가져가면 됩니다.

상태 공간은 O(N2)개이고, 각각의 상태 공간에서 값을 구하는데 상수 시간이 걸리므로 시간 복잡도는 O(N2)이 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;
vector<ll> v;
ll dp[2020][2020]; //l, r

ll ioi(int l, int r);
ll joi(int l, int r);

inline int Plus(int x){ return (x + 1) % n; }
inline int Minus(int x){ return (x + n - 1) % n; }

ll ioi(int l, int r){
	if(Plus(r) == l) return 0;
	if(v[Minus(l)] > v[Plus(r)]) return joi(Minus(l), r);
	return joi(l, Plus(r));
}

ll joi(int l, int r){
	ll &ret = dp[l][r];
	if(ret != -1) return ret;
	if(Plus(r) == l) return ret = 0;
	ll t1 = v[Minus(l)] + ioi(Minus(l), r);
	ll t2 = v[Plus(r)] + ioi(l, Plus(r));
	return ret = max(t1, t2);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; v.resize(n);
	for(int i=0; i<n; i++) cin >> v[i];
	ll ans = 0;
	memset(dp, -1, sizeof dp);
	for(int i=0; i<n; i++){
		ans = max(ans, v[i] + ioi(i, i));
	}
	cout << ans;
}