취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 18259번 문제인 Greedy Pie Eaters이다.
문제는 아래 링크를 확인하자.

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

\(dp[l][r]\)을 구간 \([l,r]\)에 포함된 파이만을 소들이 먹을 수 있을 때의 파이를 먹은 모든 소의 가중치의 합의 최댓값이라 정의하자. 이 때 문제에서 구하고자 하는 값은 \(dp[1][N]\)이 될 것이다. 

편의상 정확히 구간 \([l,r]\)의 파이를 먹어치우고자하는 소가 없는 경우 해당 구간에 \([l,r]\)의 파이를 먹어치우고자하는 가중치 0의 소가 존재한다고 생각하자. 이러한 가정을 하더라도 문제의 답에는 영향을 주지 않음을 확인하자.

구간 \([l,r]\)에 포함된 파이만을 소들이 (그 구간에서 가중치의 합이 최대가 되게끔) 파이를 먹는 과정에는 마지막으로 파이를 먹은 소가 항상 존재할 수밖에 없음을 관찰하자. 이로부터 "마지막으로 파이를 먹을 소가 파이를 먹기 전 상태"와 "마지막으로 파이를 먹을 소"에 대한 정보를 이용해 \(dp[l][r]\)의 값을 구할 점화식을 세워 문제를 해결할 것이다.

구체적으로 점화식을 세우는 방식을 서술하면 이렇다. "마지막으로 파이를 먹을 소"가 먹을 파이(중 하나)를 \(m\)이라 가정하자. 이 때, 이 소가 파이를 먹기 전까지는 \(m\) 위치에 있는 파이를 먹은 소가 존재할 수 없으므로 이 경우의 "마지막으로 파이를 먹을 소"가 파이를 먹기 전의 파이를 먹은 소들의 가중치의 합의 최댓값은 \(dp[l][m-1] + dp[m+1][r]\)이 된다. 이렇게 파이를 먹은 뒤 \(m\) 위치에 있는 파이를 먹을, 구간 \([l,r]\)에 포함되는 구간의 파이만을 먹을 최대 가중치 소를 고르면 "마지막으로 파이를 먹는 소가 \(m\) 위치의 파이를 먹을 경우"의 \(dp[l][r]\)의 최댓값을 구해낼 수 있다. 이를 \(l\) 이상 \(r\) 이하의 모든 \(m\)에 대하여 계산해 그중 최댓값을 구하면 \(dp[l][r]\)의 값을 계산할 수 있게 된다. 시간복잡도는 "\(m\) 위치에 있는 파이를 먹을, 구간 \([l,r]\)에 포함되는 구간의 파이만을 먹을 최대 가중치 소"의 가중치를 모두 알고 있다는 전제 하에 \(O(N^3)\)이 됨은 어렵지 않게 보일 수 있다.

이 과정에서 필요한 "\(m\) 위치에 있는 파이를 먹을, 구간 \([l,r]\)에 포함되는 구간의 파이만을 먹을 최대 가중치 소"의 가중치는 또다른 \(O(N^3)\) dp를 이용해 계산해낼 수 있다. 이는 어렵지 않으므로 설명을 생략한다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, M;
int seg[301][301];
int dp[301][301];
bool dpvisited[301][301];
int mx[301][301][301];
bool mxvisited[301][301][301];

int mxfunc(int l, int r, int m) {
	int& ret = mx[l][r][m];
	if (mxvisited[l][r][m]) return ret;
	mxvisited[l][r][m] = 1;

	ret = seg[l][r];
	if (l < m) ret = max(ret, mxfunc(l + 1, r, m));
	if (m < r) ret = max(ret, mxfunc(l, r - 1, m));
	
	return ret;
}

int dpfunc(int l, int r) {
	int& ret = dp[l][r];
	if (dpvisited[l][r]) return ret;
	dpvisited[l][r] = 1;

	if (l == r) return ret = seg[l][r];
	
	ret = max(ret, mxfunc(l, r, l) + dpfunc(l + 1, r));
	for (int k = l + 1; k < r; k++) {
		ret = max(ret, dpfunc(l, k - 1) + mxfunc(l, r, k) + dpfunc(k + 1, r));
	}
	ret = max(ret, dpfunc(l,r - 1) + mxfunc(l, r, r));

	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	while (M--) {
		int w, l, r; cin >> w >> l >> r;
		seg[l][r] = w;
	}

	cout << dpfunc(1, N);
}