취미로 코딩하기

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

이번에 볼 문제는 백준 25188번 문제인 1, 3, 모 나누기이다.
문제는 아래 링크를 확인하자.

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

dp[i][j]를 i~k번째 수들의 합의 최솟값이라 하자. (단, k는 i 이상 j 이하이고, 그 값이 음수라면 0을 채워넣는다.)

이제 주어진 배열을 [1,L-1], [L,R], [R+1,N]의 셋으로 쪼개고 각 구간의 dp[i][j]값들을 더한 것의 최댓값을 구하면 답을 구해낼 수 있다.

단, 위와 같이 배열을 셋으로 쪼갤 수 있으려면 배열의 크기가 3 이상이어야 하므로 크기가 2 이하인 배열은 예외처리를 해주자.

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

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

int N;
ll arr[2002];
ll dp[2002][2002]; // [i][j]: "i번에서 시작해서 k(<=j)에서 끝나는 구간합"의 최댓값

void solve() {
	for (int i = 1; i <= N; i++) {
		ll psum = 0, mx = 0;
		for (int j = i; j <= N; j++) {
			psum += arr[j];
			mx = max(mx, psum);
			dp[i][j] = mx;
		}
	}

	ll ans = 0;
	for (int L = 2; L < N; L++) {
		for (int R = L; R < N; R++) {
			ans = max(ans, dp[1][L - 1] + dp[L][R] + dp[R + 1][N]);
		}
	}

	cout << ans;
}

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

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];

	if (N == 1) cout << max(arr[1], 0LL);
	else if (N == 2) cout << max(max(arr[1], arr[2]), max(arr[1] + arr[2], 0LL));
	else solve();
}