BOJ-10714-케이크 자르기

[changicho]

10714. 케이크 자르기

링크

난이도	정답률(_%)
Gold IV	58.571

설계

동적계획법

dp[l][r] :

현재 상황까지 가져간 가장 왼쪽 위치는 l, 가장 오른쪽 위치를 r

ioi의 차례에서는 (l-1)번째와 (r+1)번째 중에서 더 큰 값을 가져가면 됩니다.

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

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

상태 공간은 O(N^2)개이고, 각각의 상태 공간에서 값을 구하는데 상수 시간이 걸리므로

시간 복잡도는 O(N^2)

정리

내 코드 (ms)	빠른 코드 (ms)
88

고생한 점

code

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cstring>

#define SIZE 2000+1

using namespace std;

int N;
int a[SIZE];
long long dp[SIZE][SIZE];
bool b[SIZE][SIZE];

static int right(int num) {
	return (num + 1) % N;
}

static int left(int num) {
	return (num + N - 1) % N;
}

long long ioi(int, int);
long long joi(int, int);

long long ioi(int l, int r) {
	if (right(r) == l) return 0;
	if (a[left(l)] > a[right(r)]) return joi(left(l), r);

	return joi(l, right(r));
}

long long joi(int l, int r) {
	if (dp[l][r] != -1) return dp[l][r];
	if (right(r) == l) return dp[l][r] = 0;

	long long t1 = a[left(l)] + ioi(left(l), r);
	long long t2 = a[right(r)] + ioi(l, right(r));
	return dp[l][r] = max(t1, t2);
}

void solution() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	memset(dp, -1, sizeof(dp));

	long long answer = 0;
	for (int i = 0; i < N; i++) {
		long long result = a[i] + ioi(i, i);
		answer = max(result, answer);
	}

	cout << answer << "\n";
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solution();

	return 0;
}