[c++] 백준 - 케이크 자르기2 10714

1. 문제

2. 입 출력

3. 예제 입출력

4. 문제 해설

dp의 문제이다. 백준 - 카드게임 문제와 비슷하다. 이 문제는 직접 게임의 형태를 구현하는 방향으로 dp를 구성해야했다. 

 

우선 문제를 읽어보면 ioi와 joi가 번갈아가면서 케이크를 가져간다. 하지만 ioi의 경우에는 둘 중 더 큰 조각만을 가져간다. 무조건 정해져있는 것이다. 하지만 이 경우 greedy처럼 더 큰 것만을 가져간다고 더 최적의 결과가 보장되는 것은 아니다. 

따라서 joi가 가져갈 때는 dp값을 통해 더 좋은 결과를 가져가야한다. 또한 재귀를 이용해 dp를 구성해야한다. 

 

우선 환형태를 어떻게 구현해야하는 지에 대해 고민을 해보았다. 

2가지 방법이 떠올랐었는데 하나는 2 5 7 8 10의 조각이 있을 경우 2 5 7 8 10 2 5 7 8 10과 같이 2번 반복해 환형태를 구현하는 것이었다. 

두 번째는 %연산을 이용하는 것이었다. 

int goLeft(int x) {
	return (x + N - 1) % N;
}
int goRight(int x) {
	return (x + 1) % N;
}

위와 같이 환형태의 좌표를 구현할 수 있는데 만약 5조각으로 나누어졌다고 한다면 0 1 2 3 4의 인덱스가 존재하고 4에서 오른쪽으로 가면 다시 0이 나와야하는 구조일 것이다. 따라서 (4 + 1 ) % N == 0이므로 다음과 같이 구현해주었다. 위의 left의 경우는 음수로 가면 안되므로 현재 좌표에 N을 더해준 후 다시 모듈러 연산을 해주었다. 

 

dp를 구성할 때는 3가지의 과정을 거쳐야한다. 

1. dp배열의 정의

2. 점화식의 정의

3. 초기값

 

나는 dp배열의 정의를 dp[start][end]에서 양 끝이 start end일 때 joi가 가져갈 수 있는 최대값으로 설정했다. 

예를 들어 dp [1][5]라면 가져갈 수 있는 양 끝 조각이 1번째 조각 5번째 조각이라는 뜻이고 2 3 4는 이미 가져갔다는 뜻이다. 

 

점화식은 게임의 형태를 구현하는 식으로 구성했다. 

ioi의 경우 cakes[start]와 cakes[end]중 더 큰 값을 가져가니까 ioi가 가져간 후 수행해야하는 작업은 더 큰 값을 ioi가 가져간 후 수행해야하는 작업이겠다. 

 

ll ioi(int start, int end) {
	//1. 만약 마지막 
	if (goRight(end) == start) return 0;
	//2. ioi는 더 큰쪽을 선택함 
	if (cakes[goRight(end)] < cakes[goLeft(start)]) {
		return joi(goLeft(start), end);
	}
	else return joi(start, goRight(end));
}

따라서 다음과 같다. 

joi의 경우는 둘 중의 값들 중 더 큰 값을 갱신해야한다. 

ll joi(int start, int end) {
	//1. 끝까지 온 경우 
	if (goRight(end) == start) return dp[start][end] = 0;
	//2. 갱신이 된 경우
	if (dp[start][end] != -1) return dp[start][end];
	//3. 더 큰 경우를 갱신한다.
	ll L = ioi(goLeft(start), end) + cakes[goLeft(start)];
	ll R = ioi(start, goRight(end)) + cakes[goRight(end)];
	return dp[start][end] = max(L, R);
}

---

5. 코드

#pragma warning (disable : 4996)

#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;

int N;
ll cakes[2020];
ll dp[2020][2020];
ll ioi(int start, int end);
ll joi(int start, int end);
int goLeft(int x) {
	return (x + N - 1) % N;
}
int goRight(int x) {
	return (x + 1) % N;
}


void input() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lld", &cakes[i]);
	}
}
int main() {
	ll ans = 0;
	input();
	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;
}

ll ioi(int start, int end) {
	//1. 만약 마지막 
	if (goRight(end) == start) return 0;
	//2. ioi는 더 큰쪽을 선택함 
	if (cakes[goRight(end)] < cakes[goLeft(start)]) {
		return joi(goLeft(start), end);
	}
	else return joi(start, goRight(end));
}
ll joi(int start, int end) {
	//1. 끝까지 온 경우 
	if (goRight(end) == start) return dp[start][end] = 0;
	//2. 갱신이 된 경우
	if (dp[start][end] != -1) return dp[start][end];
	//3. 더 큰 경우를 갱신한다.
	ll L = ioi(goLeft(start), end) + cakes[goLeft(start)];
	ll R = ioi(start, goRight(end)) + cakes[goRight(end)];
	return dp[start][end] = max(L, R);
}