[백준] 10714: 케이크 자르기 2

0. 문제 주소

 

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

10714번: 케이크 자르기 2

 

 

1. 풀이

 

 

사선 dp 문제들과 유사하게, 구간을 고려하는 점은 비슷하지만, dp 테이블의 정의를 다르게 해야 한다.

 

ll dp[MAX][MAX];
// dp[i][j] : 현재까지 i ~ j번 조각이 없어졌을 때, 남은 조각들에서 JOI가 가져올 수 있는 총 값의 최댓값 

 

문제에선 조각의 번호가 1부터 N까지이지만, modulo 연산의 편의를 위해서 0부터 N-1까지로 설정한다.

 

그리고 dp 테이블의 정의대로, IOI과 JOI의 행동을 함수로 구현한다.

 

int goright(int pos) {
	return (pos+1)%N;
}

int goleft(int pos){
	return (pos+N-1)%N;
}

ll IOI(int start, int end){
	if (goright(end) == start) return 0;
	
	if (cakes[goleft(start)] < cakes[goright(end)]) return JOI(start, goright(end));
	else return JOI(goleft(start), end);
}

ll JOI(int start, int end){
	ll &ret = dp[start][end];
	if (ret != -1) return ret;
	
	if (goright(end) == start) return ret = 0;
	
	ll L = cakes[goleft(start)] + IOI(goleft(start), end);
	ll R = cakes[goright(end)] + IOI(start, goright(end));
	
	return ret = max(L, R);
}

 

마지막으로, 맨 처음 JOI가 어느 조각을 먼저 먹을지 모든 경우를 다 고려해야 하므로,

 

    ll ans = 0;
    memset(dp, -1, sizeof(dp));
    for (int i=0;i<N;i++){
        ans = max(ans, cakes[i] + IOI(i, i));
    }
    printf("%lld\n", ans);

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <iostream>
#include <cstring>

#define MAX 2005
#define ll long long

using namespace std;

int N;
ll cakes[MAX];
ll dp[MAX][MAX];
// dp[i][j] : 현재까지 i ~ j번 조각이 없어졌을 때, 남은 조각들에서 JOI가 가져올 수 있는 총 값의 최댓값 
// 구간 이용하는 사선 dp랑 비슷하지만 보는 구간이 (i ~ j)의 여집합인 것이 다름 

int goright(int pos) {
	return (pos+1)%N;
}

int goleft(int pos){
	return (pos+N-1)%N;
}

ll IOI(int start, int end);
ll JOI(int start, int end);

ll IOI(int start, int end){
	if (goright(end) == start) return 0;
	
	if (cakes[goleft(start)] < cakes[goright(end)]) return JOI(start, goright(end));
	else return JOI(goleft(start), end);
}

ll JOI(int start, int end){
	ll &ret = dp[start][end];
	if (ret != -1) return ret;
	
	if (goright(end) == start) return ret = 0;
	
	ll L = cakes[goleft(start)] + IOI(goleft(start), end);
	ll R = cakes[goright(end)] + IOI(start, goright(end));
	
	return ret = max(L, R);
}


int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE
    
    scanf("%d", &N);
    for (int i=0;i<N;i++){
    	scanf("%lld", &cakes[i]);
	}
	
	ll ans = 0;
	memset(dp, -1, sizeof(dp));
	for (int i=0;i<N;i++){
		ans = max(ans, cakes[i] + IOI(i, i));
	}
	printf("%lld\n", ans);

    return 0;
}