BOJ 2419 사수아탕

재재

안녕하세요,
재재입니다.

boj 2419 사수아탕 문제에 대한 솔루션입니다.

(1) 문제 설명

분류 : dynamic programming

출처 : https://www.acmicpc.net/problem/2419

(2) 풀이 도출

시작점인 0을 기준으로, 방문하면서 얻을 점수를 수식화하면 다음과 같습니다.

여기서 t 는 각 장소에 도착하는 시간을, p는 방문 지역 순서를 의미합니다.
$(m-t_{p_1}) + (m-t_{p_2}) + … + (m-t_{p_x}) = mx – \Sigma t$

그리고 여기서 1 움직일 때 마다 모든 사탕이 1개씩 줄어든다는 정보를 활용해서 전개하면
$\Sigma t = x\Delta t_{p_1} + (x-1)\Delta t_{p_2} + … + \Delta t_{p_x}$
$\Delta t_{p_1} = \vert 0 – p_1 \vert$

이제 이 식은 점화식 형태가 완성되었으며,
top down approach 와 bottom up 모두 가능합니다.

다만 x 를 정해줘야하는 문제가 있기 때문에,
최적이 되는 x 를 모두 시도해도 시간 복잡도는
$O(n^3)$ 입니다.

이제 조심해야하는 부분은 시작점이 0인 곳에도 사탕이 있을 수 있다는 것이고,
현재 상태가 왼쪽 끝인지 우측 끝인지 정해주면 되기 때문에 아래와 같이 상태공간을 정할 수 있습니다.

dp[le][ri][is_right] : 현재 구간 le부터 ri까지 방문했고,
한 쪽 끝에 서있을 때 앞으로 얻을 사탕의 최적

다만,
위 점화식에서 부호가 음수기 때문에 사탕의 최적은,
움직일 수 있는 거리의 최소로 구하시면 되겠습니다.

(3) 정답 코드

	#include <cstdio>
	#include <memory.h>
	#include <algorithm>
	using namespace std;

	int n;
	int dp[303][303][2];
	int e[303];

	int dy(int l, int r, int is_right, int limit) {
	if (limit == 0)return 0;
	int &ret = dp[l][r][is_right];
	if (ret != -1)return ret;
	ret = 1e+9;

	if (l) {
	ret = min(ret, dy(l - 1, r, 0, limit - 1) + \
	(limit * (e[is_right == 1 ? r : l] - e[l - 1])));
	}

	if (r < n-1) {
	ret = min(ret, dy(l, r + 1, 1, limit - 1) + \
	(limit * (e[r + 1] - e[is_right == 1 ? r : l])));
	}
	return ret;
	}

	int main() {
	int m;
	scanf("%d %d", &n, &m);

	int real_n = n;
	int already_eat = 0;
	bool need_zero = true;

	for (int i = 0; i < n; i++)
	scanf("%d", &e[i]);
	if (e[i] == 0)need_zero = false;
	}

	if (need_zero) {
	e[n] = 0;
	n++;
	}
	else {
	already_eat = 1;
	}
	sort(e, e + n);

	int l = -1;
	for (int i = 0; i < n && l == -1; i++)if (e[i] == 0) {
	l = i;
	}

	int ans = 0;
	for (int limit = 1; limit <= real_n; limit++) {
	memset(dp, 0xff, sizeof(dp));
	int cur = dy(l, l, 0, limit - already_eat);
	ans = max(ans, m*limit - cur);
	}
	printf("%d\n", ans);
	}

	/*
	3 15
	6
	-3
	1

	3 steps
	-3 -> 1 -> 6
	// 12 + 8 + 3

	1 -> 6 -> -3
	// 14 + 9 + 0

	1 -> -3 -> 6
	// 14 + 10 + 1 (25)

	2 steps
	1 -> -3 (24)
	*/

view raw boj2419.cc hosted with

by GitHub

BOJ 2419 사수아탕