BOJ10714 케이크 자르기 2

10714번 케이크 자르기 2

 

 

 

 

자를 수 있는 케이크 조각의 크기가 주어질 때,

JOI는 최선을 다해 케이크를 자르고, IOI는 양 끝 조각 중 무조건 큰 조각을 자른다.

JOI가 얻을 수 있는 조각 합의 최댓값을 구해야 한다.

 

최선을 다하는 문제와 비슷하다. 다른 점은

 

JOI만 최선을 다한다

⇒ dp배열에 두 명이 가진 케이크 양을 저장할 필요 없이 JOI가 얻게 된 조각 합의 양만 저장하면 된다.

 

케이크 조각은 직선형 배열이 아닌 원형 배열이다. 즉 시작과 끝이 정해져있지 않다

⇒ i, j의 대소에 관계없이 전체 dp 배열을 채워야 한다. 가령 N=5일 때

    dp[ 2 ][ 4 ]는 2, 3, 4번째 조각이 남아있을 때

    dp[ 4 ][ 2 ]는 4, 5, 1, 2번째 조각이 남아있을 때 JOI가 얻은 케이크 조각 합의 최댓값이 될 것

 

 

STEP 1. 케이크 조각이 1개, 2개 남은 경우만 처리

 

 

STEP 2. i~j번째 케이크 조각으로 JOI가 얻을 수 있는 조각 합의 최댓값 계산

JOI가 조각 i를 가진다면 IOI는 조각 i+1, j 중 큰 것을 가져갈 것이다.

IOI가 무엇을 가져갔느냐에 따라 JOI는 i+2~j번째 or i+1~j-1번째 케이크 조각으로 자르기를 할 것 (3행)

JOI가 조각 j를 가진다면 IOI는 조각 i, j-1 중 큰 것을 가져가고,

이후 경우에 따라 JOI는 i+1~j-1번째 or i~j-2번째 케이크 조각으로 자르기를 할 것 (4행)

	i1 = (i + 1) % N, i2 = (i + 2) % N;
	j1 = (j - 1 + N) % N, j2 = (j - 2 + N) % N, j %= N;
	tmp1 = cake[i] + ((cake[i1] > cake[j]) ? dp[i2][j] : dp[i1][j1]);
	tmp2 = cake[j] + ((cake[i] > cake[j1]) ? dp[i1][j1] : dp[i][j2]);
	//when J eats cake[i], I eats max(cake[i+1], cake[j])
	//when J eats cake[j], I eats max(cake[i], cake[j-1])

* STEP 1에서 케이크 조각이 1개, 2개 남은 경우를 먼저 처리한 이유이기도 함. i에 대해 i-2, i+2가 필요해서

* 인덱스 계산할 때 N에 대해 MOD연산 해줘야 한다.

 

 

STEP 3. 요구한 답을 출력한다.

dp[ 0 ][ N-1 ], dp[ 1 ][ 0 ], dp[ 2 ][ 1 ],… 중 최댓값을 출력하자

 

 

 

코드 

 

#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
long long dp[2000][2000];
//dp[i][j]: i~j 에서 J가 먹을 수 있는 케이크 최대 양
//dp[2][7]: 2 3 4 5 6 7
//dp[7][2]: 7 8 9...1 2

int main() {
    long long cake[2001], tmp1, tmp2;
	int N, i1, i2, j1, j2;
	scanf("%d", &N);
    
	//STEP 1. [i][i], [i-1][i]
	for (int i = 0; i < N; ++i) scanf("%lld", &cake[i]), dp[i][i] = cake[i];
	for (int i = 1; i < N; ++i) dp[i - 1][i] = max(cake[i - 1], cake[i]);
	dp[N - 1][0] = max(cake[N - 1], cake[0]);
    
	//STEP 2. Else
	for (int n = 2; n < N; ++n) {
		for (int i = 0, j = n; i < N; ++i, ++j) {
			i1 = (i + 1) % N, i2 = (i + 2) % N;
			j1 = (j - 1 + N) % N, j2 = (j - 2 + N) % N, j %= N;
			tmp1 = cake[i] + ((cake[i1] > cake[j]) ? dp[i2][j] : dp[i1][j1]);
			tmp2 = cake[j] + ((cake[i] > cake[j1]) ? dp[i1][j1] : dp[i][j2]);
			//when J eats cake[i], I eats max(cake[i+1], cake[j])
			//when J eats cake[j], I eats max(cake[i], cake[j-1])			
            
			dp[i][j] = max(tmp1, tmp2);
		}
	}
    
	//STEP 3. Print MAX
	long long MAX = dp[0][N - 1];
	for (int i = 1; i < N; ++i) if (MAX < dp[i][i - 1]) MAX = dp[i][i - 1];
	printf("%lld", MAX);

	return 0;
}

 

코드가 짧아 명료하게 푼 기분