[BOJ] 2118 - 두 개의 탑

문제 링크

생각하건대, 분명 이렇게 푸는 것을 의도한 문제가 아닐 것이다.
시간복잡도를 약간 넘을 위험이 있었지만 내 컴퓨터에서 돌려봤을 때 초과가 되지 않을 듯 해서 냈고 아슬아슬하게 통과가 되었다.
분명 다른 어떤 방법으로 획기적으로 시간복잡도를 줄일 수 있는 방법이 있을 것인데, 생각하지 않겠다!(당당)
… 아무튼 그런 이유로 그냥 완전탐색으로 풀었다.

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int sum[50005], ans;

int main(void) {
	int n;
	scanf("%d", &n);
	scanf("%d", sum + 1);
	for (int i = 2; i <= n; i++) {
		scanf("%d", sum + i);
		sum[i] += sum[i - 1];
	}
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			ans = max(ans, min(sum[j] - sum[i - 1], sum[n] - sum[j] + sum[i - 1]));
		}
	}
	printf("%d", ans);
	return 0;
}