취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10714번 문제인 케이크 자르기 2이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/10714

주어진 원형 수열을 각각의 위치에서 끊으면 선형 수열이 됨을 관찰하자. 또한, 이러한 선형수열에서 양 끝의 원소에 대해 문제에서 주어진 규칙과 같이 케이크를 가져가는 것은 원형 수열에서 첫 조각을 빼고 난 뒤의 일과 대응시킬 수 있다.

따라서 문제의 답은 주어진 원형 수열을 각각의 위치에서 끊은 각각의 경우를 조사해 구할 수 있다.

한편, 선형 배열에서의 주어진 문제는 구간DP로 어렵지 않게 풀 수 있으므로 문제가 해결된다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll N, ans;
ll A[2000];
ll dp[2000][2000];
bool visited[2000][2000];

ll func2(int L, int R);

ll func1(int L, int R) {
    if (L == N) L = 0;
    if (R < 0) R = N - 1; 
    if (visited[L][R]) return dp[L][R];
    visited[L][R] = 1;
    if (L == R) return dp[L][R] = A[L];
    else return dp[L][R] = max(A[L] + func2(L + 1, R), A[R] + func2(L, R - 1));
}

ll func2(int L, int R) {
    if (L == N) L = 0;
    if (R < 0) R = N - 1; 
    if (visited[L][R]) return dp[L][R];
    visited[L][R] = 1;
    if (L == R) return 0;
    if (A[L] > A[R]) return dp[L][R] = func1(L + 1, R);
    else return dp[L][R] = func1(L, R - 1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    ans = func1(0, N - 1);
    for (int i = 1; i < N; i++) ans = max(ans, func1(i, i - 1));

    cout << ans;
}