# 10714. 케이크 자르기 [링크](https://www.acmicpc.net/problem/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 ```cpp #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; } ```
Activity