[BOJ 10714] 케이크 자르기 2

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

10714번: 케이크 자르기 2

 

- 문제 요약

 

JOI군과 IOI양은 케이크를 나눠먹으려 한다.

케이크는 둥그런 모양을 하고 있다.

케이크를 N 개의 조각으로 나눈 뒤, 각 조각마다 1부터 N까지 반시계방향으로 번호를 매긴다.

즉, 1 ≦ i ≦ N에 대해, i 번째 조각은 i - 1 번째와 i + 1 번째 조각과 인접해 있다.

(단, 0번째는 N 번째, N + 1 번째는 1번째로 간주한다).

i 번째 조각의 크기는 Ai이지만, 칼질이 서툴러 Ai가 모두 다른 값을 가지게 되었다.

이 N개를 JOI 군과 IOI 양이 나누기로 하였다. 나누는 방법은 다음과 같다.

1. 먼저, JOI 군이 N 개의 조각 중 원하는 것 하나를 가져간다.
2. 그 뒤, IOI 양으로부터 시작해 IOI 양과 JOI 군은 번갈아가며 남은 조각을 하나씩 가져간다. 단, 인접한 조각 중 하나 이상의 조각이 이미 선택된 경우에만 가져갈 수 있다. 가져갈 수 있는 조각이 여러 개 있을 때엔, IOI 양은 그중 가장 큰 조각을 가져가고, JOI 군은 원하는 조각을 가져갈 수 있다.

JOI 군은 자신이 가져온 조각들 크기의 합을 최대화하고 싶다.

케이크의 조각 수 N과, N 개의 조각의 크기에 대한 정보가 주어질 때, JOI 군이 가져올 수 있는 조각들의 합계의 최대치를 구하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

재귀 DP로 문제에 나와있는 룰을 그대로 따라 하면 풀 수 있는 문제입니다.

DP 배열의 정의는 아래와 같습니다.

dp[i][j] : 현재 남은 조각의 가장 왼쪽이 i, 가장 오른쪽이 j일 때 JOI군이 가져올 수 있는 조각의 최대 합계

JOI군이 가져올 수 있는 조각들의 합계를 최대화해야 하므로, IOI양의 차례일 때는 (i-1) 번째 조각과 (j+1) 번째 조각 중에 더 큰 값을, JOI군의 차례일 때는 (i-1)번째 조각과 (j+1)번째 조각을 가져갔을 때 결괏값이 더 큰 쪽을 고르면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 2001
typedef long long ll;
int n;
ll arr[MAX],dp[MAX][MAX],result;

ll ioi(int a,int b);
ll joi(int a,int b);

int l(int x){
	return (x+1)%n;
}

int r(int x){
	return (x-1+n)%n;
}

ll ioi(int a,int b){
	if(l(b)==a){
		return 0;
	}
	if(arr[r(a)]>arr[l(b)]){
		return joi(r(a),b);
	}
	return joi(a,l(b));
}

ll joi(int a,int b){
	ll &ret=dp[a][b];
	if(ret!=-1){
		return ret;
	}
	if(l(b)==a){
		return ret=0;
	}
	ll aa=arr[r(a)]+ioi(r(a),b);
	ll bb=arr[l(b)]+ioi(a,l(b));
	return ret=max(aa,bb);
}

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

코드 제출 결과