BOJ-2118 두 개의 탑

필요한 지식

1. 구간합

접근

• 완전탐색의 접근은 시간초과다.

• 빠른 연산을 위해 구간합 배열을 가지고 있어야하는데, 이 문제의 경우 원형으로 이어져있다. 따라서 구간합 배열의 길이를 2*n만큼 구성하고 값을 채워준다.

• 이렇게 구간합 배열을 구성하고 나면 1번지점 에서 3번 지점까지 시계방향으로 가는 거리는 arr[n+3]-arr[n] 반시계방향으로 가는 거리는 arr[n+1]-arr[2] 로 구할 수 있다.

• 1번 지점에서 1보다 뒤에있는 지점들과의 거리계산을 해준다면 n번째는 자기번호 보다 작은 지점과의 거리는 계산해 줄 필요가없다.

코드(C++)

#include <iostream>
#include <algorithm>
using namespace std;
int arr[100001], ans = 0;
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		arr[i + n] = arr[i];
	}
	for (int i = 1; i < 2 * n; i++) arr[i] += arr[i - 1];
	for (int i = n; i < 2 * n; i++) {
		for (int j = i - n + 1; j < n; j++) {
			ans = max(ans, min(arr[i] - arr[j], arr[n + j] - arr[i]));
		}
	}
	cout << ans;
	return 0;
}

결과