BOJ 2419 - 사수아탕

BOJ 2419 - 사수아탕

[분류 - 다이나믹 프로그래밍]

  어메이징한 문제다..

  이걸 어떻게 눈치채고 문제를 푸나 싶다 하하하.. 너무 으렵다

  처음에 접근했던 잘못된 방식은 x축으로 정렬을 하고, 거기서 몇 번째를 뜻하는 구간 [l, r]을 잡고 [l-1, r] 또는 [l, r+1]을 부분 문제로 잡는다. 여기서는 왼쪽에서 끝났는지, 오른쪽에서 끝났는지를 알 수 있게끔 구성한다. 그리고 기저 사례를 왼쪽으로 더 이상 갈 수 없고 오른쪽으로도 더 이상 갈 수 없는 경우로 잡는다. 마지막으로 구간 [l, r]에서 몇 초에 도착을 했는지도 저장하도록 해서 거기서 먹을 수 있는 사탕의 수를 최대로 하는 방식으로 하면~ 메모리 + 시간 초과를 세트로 받을 수 있다.

풀이)

  자 먼저 x축에 대해 정렬하고, 특정 구간 [l, r] 상태를 왼쪽 오른쪽 방향(d)을 포함해서 (d, [l, r])로 표현해보자.

  전제 1) [l, r]에서 움직일 수 있는 곳은 한 칸 [l-1, r] 또는 [l, r-1] 중에서 골라야만 최적의 답을 구할 수 있다.

  전제 1 증명) 랄까 할 것도 없는 것이 [l-2, r]으로 2칸을 이동했다고 하자. 그러면 그 사이에 있는 사탕을 안 먹는 것이 매우 손해다. x 축 기준으로 정렬을 했기 때문에 안먹고 지나치는 사탕 바구니는 없다고 생각하는 것이다.

  전제 2) 왼쪽 오른쪽 방향을 선택하면 갈 수 있는 사탕 바구니 범위가 현재와 같거나 축소된다.

  전제 2 증명) 중복되는 위치가 없기 때문에 어디로 가든 시간이 지나며 그에 따라 사탕이 줄어든다. 그러면 사탕 바구니에 대해서는 어떤지 생각해보자. 현재 구간 [l, r]에 대해 갈 수 없는 사탕 바구니는 알 수 있으며, 얼마나 더 방문할 지도 내가 선택할 수 있다. 따라서 범위가 현재와 같거나 축소되는 것은 자명하다.

  전제 3) 현재 상태에서 방향 선택하지 않고 끝까지 머무는 상태를 유지하면 이 때의 사탕 개수는 최적해의 부분 집합이 된다.

  전제 3 증명) 이 말은 어느 사탕 바구니에 갈 수 있어도 선택하지 않는다는 말이기에 최적해의 부분 집합임은 자명하다

  전제 4) 사탕 바구니 k를 선택하여 최적해 x개를 먹는 것은 m*k개의 사탕에서 줄어들 사탕 y개를 최소화하는 것과 동치이다.

  전제 4 증명) k개를 골랐다는 것은 초기 상태 m*k개의 사탕이 있단 소리다. 여기서 어떻게 움직이느냐에 따라 최종 사탕 x개를 먹는다는 것인데, 여기서 움직일 때 사탕수를 줄어드는 것을 최소화하는 것이 곧 최대 사탕을 먹는 것이므로

x = m*k-y임을 알 수 있다.

  알고리즘은 아래와 같습니다.

  1. 방문할 사탕 바구니 k를 고정해놓습니다(전제 2, 3). 시작점에 사탕 바구니가 있을 수 있으니 이 점에 유의합시다.

  2. 시작점 s에 대해 상태 (d, [l, r])을 설정하여 (왼쪽, [l-1, r]) 또는 (오른쪽, [l, r+1])을 부분 문제로 놓고 k개를 방문할 때까지 다이나믹을 진행합니다(전제 1). 여기서 중요한 점은 사탕이 다 사라져 없어져버린다고 해도 k개를 반드시 방문하게끔 합니다. 여기서 사라진 사탕을 최소화하는 부분 문제를 선택합니다(전제 4).

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 301;
int n, m, s, p[MAX_N], dp[2][MAX_N][MAX_N];
int rec(int w, int l, int r, int cnt) {
	if (!cnt) return 0;
	int& ret = dp[w][l][r];
	if (ret != -1) return ret;
	ret = 1LL << 31 - 1;
	if (l) 
		ret = cnt * ((w ? p[r] : p[l]) - p[l - 1]) + rec(0, l - 1, r, cnt - 1);
	if (r < n - 1) 
		ret = min(ret, cnt * (p[r + 1] - (w ? p[r] : p[l])) + rec(1, l, r + 1, cnt - 1));
	return ret;
}
int main() {
	int ans = 0, i, can = 0;
	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%d", &p[i]);
		can |= p[i] == 0;
	}
	if (!can) {
		p[n] = 0;
		n += 1;
	}
	
	sort(p, p + n);
	s = lower_bound(p, p + n, 0) - p;
	for (i = 0; i < n; i++) {
		memset(dp, -1, sizeof dp);
		ans = max(ans, m * i - rec(0, s, s, i));
	}
	printf("%d", ans + can*m);

	return 0;
}