JOI 2015 2번 - ケーキの切り分け２ (Cake 2) 풀이

 

[JOI 2015 2번 - ケーキの切り分け２ (Cake 2)]

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

10714번: 케이크 자르기 2

 

JOI 군의 선택은 2가지로 나누어질 수 있는 데 반해, IOI 양의 선택은 1가지로 제한되기 때문에 문제가 조금 쉬워졌습니다. 다음과 같이 dp식을 정의해봅시다.

• $\textrm{dp[pos][left][right]}$ : 지금이 $\textrm{pos}$의 차례이고, $\textrm{left}$번째 케이크 조각과 $\textrm{right}$번째 케이크 조각을 선택할 수 있을 때, JOI 군이 가져올 수 있는 케이크 조각들의 합계의 최대치

여기서 $\textrm{pos}$가 0일 때는 JOI 군의 차례임을, 1일 때는 IOI 양의 차례임을 나타낸다고 합시다.

 

$\textrm{left}$와 $\textrm{right}$는 구체적으로 어떻게 결정해야 할까요 ?

JOI 군이 처음 선택한 케이크 조각의 번호가 $k$($0 \leq k < n$)라고 합시다. 이때 $\textrm{left}$는 $k-1$로, $\textrm{right}$는 $k+1$로 나타낼 수 있는데, 케이크 조각의 번호는 항상 $[0, n)$을 만족해야 하므로, $\textrm{left}$는 $(k-1+n)$ % $n$, $\textrm{right}$는 $(k+1)$ % $n$으로 나타내야 합니다.

 

 

지금이 JOI 군의 선택(첫 선택이 아님)이라고 합시다. JOI 군이 $\textrm{left}$번째 케이크 조각을 선택한다면 다음 차례에서 IOI 양은 $( \textrm{left}-1+n)$ % $n$번째 케이크 조각과 $\textrm{right}$번째 케이크 조각 둘 중 최대 조각을 선택해야 하고, $\textrm{right}$번째 케이크 조각을 선택한다면 다음 차례에서 IOI 양은 $\textrm{left}$번째 케이크 조각과 $( \textrm{right}+1)$ % $n$번째 케이크 조각 둘 중 최대 조각을 선택해야 합니다. 이를 다음과 같은 코드로 나타낼 수 있습니다.

ll go(int pos, int l, int r)
{
	ll& ret = dp[pos][l][r];
	if(ret != -1)
		return ret;

	ret = 0;
	if(pos == 0)
	{
		ret = max(ret, go((pos+1)%2, (l-1+n)%n, r) + cake[l]);
		ret = max(ret, go((pos+1)%2, l, (r+1)%n) + cake[r]);
	}

	return ret;
}

 

 

그런데 만약 $l$과 $r$이 같은 상황이라면 어떻게 해야 할까요 ?

이번이 마지막 조각이므로 다음 차례로 넘길 필요가 없습니다. 따라서 코드를 다음과 같이 변경해 줍시다.

ll go(int pos, int l, int r)
{
	ll& ret = dp[pos][l][r];
	if(ret != -1)
		return ret;

	ret = 0;
	if(pos == 0)
	{
		if(l != r)
		{
			ret = max(ret, go((pos+1)%2, (l-1+n)%n, r) + cake[l]);
			ret = max(ret, go((pos+1)%2, l, (r+1)%n) + cake[r]);
		}
		else
			ret = cake[l];
	}

	return ret;
}

 

 

$\textrm{pos}$가 1일 때에는, 즉 IOI 양의 차례일 때는, 선택하고자 하는 케이크 조각의 크기를 더할 필요가 없습니다. dp식의 정의가 'JOI 군'이 가져올 수 있는 케이크 조각들의 합계의 최대치로 설정되어있기 때문입니다. 따라서 dp계산은 다음과 같이 마무리됩니다.

ll go(int pos, int l, int r)
{
	ll& ret = dp[pos][l][r];
	if(ret != -1)
		return ret;

	ret = 0;
	if(pos == 0)
	{
		if(l != r)
		{
			ret = max(ret, go((pos+1)%2, (l-1+n)%n, r) + cake[l]);
			ret = max(ret, go((pos+1)%2, l, (r+1)%n) + cake[r]);
		}
		else
			ret = cake[l];
	}
	else if(l != r)
	{
		if(cake[l] > cake[r])
			return ret = go((pos+1)%2, (l-1+n)%n, r);
		return ret = go((pos+1)%2, l, (r+1)%n);
	}

	return ret;
}

 

 

JOI 군이 처음에 선택할 수 있는 케이크 조각을 차례대로 순회하면서 dp식을 계산해줍시다. 가령 $i$($0 \leq i < n$)번째 케이크 조각을 처음에 선택한다면, 이때 JOI 군이 가져올 수 있는 케이크 조각들의 합계의 최대치는 다음과 같겠죠.

cake[i] + go(1, (i-1+n)%n, (i+1)%n)