[BOJ 24940 // C++] Split the GSHS

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

 

이번에 볼 문제는 백준 24940번 문제인 Split the GSHS이다.
문제는 아래 링크를 확인하자.

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

24940번: Split the GSHS

dp[L][R]을 L번 학생부터 R번 학생들까지를 한 무리로 묶을 때의 가장 많이 떨어뜨릴 수 있는 친밀도의 절댓값이라 하자. 이 때 문제에서 구하고자하는 값은 -dp[1][N]로 나타낼 수 있다.

 

L번 학생부터 R번 학생들까지 한 무리로 묶이기 위해서는 이전 단계에서 인접하게 둘로 나뉜 두 학생의 무리가 뭉쳐져야 하므로 그 가능한 모든 경우의 수를 살피는 것으로 dp[L][R]을 계산해낼 수 있다.

구체적으로 식으로 표현하면 dp[L][R]은 dp[L][M] + dp[M+1][R] - min((L~M의 합)*(M+1~R의 합), 0) (M은 L 이상 R 미만)과 같은 식을 찾아낼 수 있다.

 

위 식에 등장하는 구간의 원소의 합은 prefix sum을 이용하여 빠르게 계산해낼 수 있다.

 

dp[L][R]의 값을 한번 계산하면 더이상 추가로 그 값을 계산해볼 필요는 없으므로, memoization을 이용하여 효율적인 구현을 하는 것으로 O(N^3)에 문제를 해결할 수 있다.

 

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

#include <iostream>
using namespace std;
typedef long long ll;

int N;
ll arr[81];
ll psum[81];
ll dp[81][81];
bool visited[81][81];

void func(int L, int R) {
	ll ret = 0;
	visited[L][R] = 1;
	
	for (int mid = L; mid < R; mid++) {
		if (!visited[L][mid]) func(L, mid);
		if (!visited[mid + 1][R]) func(mid + 1, R);
		ll tmp = dp[L][mid] + dp[mid + 1][R] - min((psum[mid] - psum[L - 1]) * (psum[R] - psum[mid]), 0LL);
		ret = max(ret, tmp);
	}
	
	dp[L][R] = ret;
}

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		ll& x = arr[i];
		cin >> x;
		psum[i] = psum[i - 1] + x;
	}

	func(1, N);

	cout << -dp[1][N];
}