문제 설명
N 개의 지점에 두 개의 탑을 세워 반시계 방향과 시계 방향의 거리의 최솟값 중 최대를 구하는 문제입니다.
풀이
N 개의 지점들이 주어지고 그 사이 거리들이 주어집니다.
지점들은 차례대로 원으로 이어져있어 두 지점의 거리를 반시계 방향, 시계 방향으로 거리를 구할 수 있는데 이 거리 중 최솟값을 두 지점의 거리라고 합니다.
N 개의 지점 중에 두 개의 지점에 탑을 세웠을 때 최대의 거리를 구하면 됩니다.
두 지점에 탑을 세울 수 있는 모든 경우를 봐서 최댓값을 구하게 되면 시간 복잡도가 O(n2)입니다.
그런데 저희가 모든 경우를 볼 필요 없습니다.
탑 하나는 순서대로 1 ~ N 지점에 세우도록 하겠습니다.
이제 다른 탑 하나를 세워야 하는데 이분 탐색을 이용하겠습니다.
이분 탐색을 어떻게 쓸까요?
첫 번째 탑을 1에 세우고 이제 다른 탑 하나를 세워야 합니다.
탑 하나를 1에 세웠으면 중복이 되지 않게 다른 탑 하나를 2~N에 세우겠습니다.
도시가 원으로 이어져있기 때문에 임의의 두 도시를 세웠을 때 반시계 거리와 시계 거리의 합은 항상 동일하고
그러므로 시계방향 거리와 반시계 방향 거리를 최소화하면 가장 최대의 거리를 구할 수 있습니다.
(반시계 방향 거리 + 시계 방향 거리) = 모든 도시의 거리 합
탑을 하나는 고정이니 다른 탑을 세울 때 시계 방향 거리와 반시계 방향 거리를 구합니다.
두 번째 탑을 그 위치보다 시계 방향으로 있는 곳에 세우게 되면 시계방향 거리가 늘어나고 반시계 방향 거리가 줄어듭니다.
두 번째 탑을 그 위치보다 반시계 방향으로 있는 곳에 세우게 되면 반시계 방향 거리가 늘어나고 시계방향 거리가 줄어듭니다.
그래서 최대한 시계방향과 반시계 방향 거리를 동일하게 맞춰야 최대 거리를 구할 수 있으므로
반 시계 방향 거리가 더 작을 땐 두 번째 탑을 현 위치보다 반시계 방향 쪽으로
시계 방향 거리가 더 작을 땐 두 번째 탑을 현 위치보다 시계 방향 쪽으로 세우면 됩니다.
sum[n] = 1 ~ n + 1의 시계 방향 거리
arr[n] = (n, n + 1)의 거리
one = 첫 번째 탑의 위치
one = 2일 때 두 탑의 거리를 최대로 하는 탑을 세워보도록 하겠습니다.
두 방향의 거리는 sum[mid] - sum[one - 1], 모든 거리 합 - (sum[mid] - sum[one])으로 구할 수 있습니다.
거리를 구하니 (14, 10)입니다.
더 왼쪽으로 가면 차이를 줄일 수 있습니다.
두 방향 거리가 (7, 17)입니다.
오른쪽으로 가야 차이를 줄일 수 있습니다.
(12, 12)입니다.
탑 하나가 1에 있을 때 최대 거리는 12입니다.
이런 식으로 탑 하나를 1~N에 세우고
다른 하나를 이분 탐색을 하며 최대 거리를 찾아주시면 됩니다!!
다른 분들 문제 풀이들을 보면 저와 다르게 푸신 것 같아서
제 풀이는 ‘이런 풀이도 있다’라고 생각하시고 한번봐주시면 좋을 것 같아요 ㅎㅎ
그리고 이 문제가 완전 탐색으로도 풀리는데
O(n^2)이지만 연산이 최댓값만 비교하면 돼서 시간이 아슬아슬하게 되는 것 같습니다.
간단한 연산이라 가능한 것 같습니다.
소스 코드
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int main() {
FIO;
int n;
cin >> n;
int sum[50005] = {}, ans = 0;
FOR(i, 1, n) {
int x;
cin >> x;
sum[i] = sum[i - 1] + x;
}
FOR(i, 1, n) {
int l = i, r = n;
while (l <= r) {
int m = l + r >> 1;
int a = sum[m] - sum[i - 1];
int b = sum[n] - a;
if (a < b) l = m + 1;
else r = m - 1;
ans = max(ans,min(a, b));
}
}
cout << ans << '\n';
return 0;
}