백준 10714 케이크 자르기 2 - C++

참 재미있는 문제이다.

손으로 풀면 한참 걸릴 것이란게 예측되는가?

그렇다면 손으로 푸는 방식을 컴퓨터에게 시키면

금방 풀어줄 것이다. 

 

J군은 처음에 아무거나 하나 뽑을 수 있고,

하나를 뽑은 후에는

J군과 I양 모두 가져간 조각 옆에 있는 조각만 가져갈 수 있다.

 

J군은 당장 왼쪽 케이크가 오른쪽 케이크보다 작더라도

총합이 크다면 왼쪽 케이크를 선택할 수 있다.

J군의 자유의지를 통해서 

바보 같이 큰 것만 가져가는 I양보다

훨씬 큰 이득을 챙겨보자.

 

언뜻 보기에는 이해가 안 갈 수 있다.

하지만 이 문제는 전형적인 DP(Dynamic Programming) 문제이다.

 

어떤 조각을 처음으로 뽑았을 때

J가 가져갈 수 있는 가장 큰 총합만 알면 되기 때문이다.

이를 재귀를 통해 구현한다.

재귀는 말로 푸는 것이 헷갈리지 않는다.

 

우선 케이크가 N개의 조각이므로 

케이크 0번째 부터 J가 골랐다고 가정한다.

그럼 I의 선택은 J의 선택 왼쪽/오른쪽 중 큰 것만 가져가므로

I의 선택은 항상 고정되어 있다.

J의 선택은 I의 선택 후 

남은 총량에서 가장 많이 가져가는 경우이므로

dp[l][r] 에 l과 r 상태일 때 가져갈 수 있는 최대값을 저장하여 

현재 상태에서 dp[l][r] 값만 보고 더 계산하지 않고 

최대값을 알 수 있다.

 

즉 점화식으로 따지자면

1. cake 1 번째 선택 + cake[0][2] 는 cake 1을 처음 뽑을 때 J가 가질 수 있는 최대값이다.

2. dp[n][n] = 0, dp[i][N-i-1] = min(cake[i], cake[N-i-1] ) 이다. 

예를 들어 케이크 3조각이 있고, 0,1,2 번째라고 할 때, J가 1번을 골랐으면 나머지 0,2번째 중 I가

더 큰 것을 가져갈 것이므로, 재귀함수의 기저값은 cake 조각이 2조각 남았을 때이다.

3. 종합적으로 최대값 = max( i, cake[i-1][i+1]) 이고 i = 0~ N 이며, i+1 >= N 이거나 i-1<0 일 경우

케이크가 동그라미이므로 한 바퀴 돌았다고 가정하여 i를 바꿔준다.

 

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 2001;
const int MAXA = 1000000001;

vector<ll> cake;
ll dp[MAXN][MAXN];

int N, A;

int Choose_left(int l)
{
	return (l - 1+N) % N;
}
int Choose_right(int r)
{
	return (r + 1) % N;
}
ll JOI(int, int);
ll IOI(int l, int r)
{
	if (Choose_left(l) == r) return 0;
	return (cake[Choose_left(l)] > cake[Choose_right(r)]) ? JOI(Choose_left(l),r):JOI(l,Choose_right(r));

}
ll JOI(int l, int r)
{
	ll& ret = dp[l][r];
	if (ret != -1) return ret;
	if (l == Choose_right(r)) return 0;
	ll r1 = cake[Choose_left(l)] + IOI(Choose_left(l), r);
	ll r2 = cake[Choose_right(r)] + IOI(l, Choose_right(r));
	return ret=max(r1, r2);
}



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

	}
	cout << ans;

}