두개의 탑
1번부터 N번까지의 지점이 있다. 각각의 지점들은 차례로, 그리고 원형으로 연결되어 있다. 이 지점들 중 두 곳에 두 개의 탑을 세우려고 하는데, 두 탑의 거리가 최대가 되도록 만들려고 한다.
지점들이 원형으로 연결되어 있기 때문에, 두 지점 사이에는 시계방향과 반시계방향의 두 경로가 존재한다. 두 지점 사이의 거리를 잴 때에는, 이러한 값들 중에서 더 작은 값을 거리로 한다.
연결되어 있는 두 지점 사이의 거리가 주어졌을 때, 두 탑의 거리의 최댓값을 계산하는 프로그램을 작성하시오.
입력
첫째 줄에 지점의 개수 N(2 ≤ N ≤ 50,000)이 주어진다. 다음 N개의 줄에는 차례로 두 지점 사이의 거리가 양의 정수로 주어진다. 전체 거리의 총 합은 1,000,000,000을 넘지 않는다.
출력
첫째 줄에 답을 출력한다.
풀이
예제를 도시화하면 위와 같습니다. 만약 1번과 2번이 선택되었다면, 거리는 1이지만, 반대방향까지 포함하여 14도 존재합니다. 이중에 1이 제일 가까우므로 1번과 2번의 거리는 1이됩니다. 이를 이제, 오른쪽 거리와 왼쪽 거리라고 하겠습니다.
실제로 주어지는 것은 거리입니다. 배열에서 순서대로 1번과 2번, 2번과 3번, 3번과 4번... 순으로 거리정보가 전달됩니다. 즉, 배열의 첫번째 인덱스에 해당하는 1과 그 나머지 거리의 합인 14가 1번과 2번의 거리입니다.
여기서, 투 포인터를 이용하여 시작과 끝을 표현하겠습니다. 현재 배열은 아래와 같습니다.
- 1 ~ 2 : 1
- 2 ~ 3 : 2
- 3 ~ 4 : 3
- 4 ~ 5 : 4
- 5 ~ 1 : 5
start 포인트는 시작점을 가르키겠습니다. end는 끝점입니다. 만약 start, end가 모두 1이라면, 1번부터 2번까지를 가르키는 의미입니다. 만약 start가 1인데, end가 4라면 1번부터 5번까지의 거리를 나타내게 됩니다.
각 지점의 거리는 누적합을 이용해서 미리 합계를 계산할 것입니다. 투 포인터를 계산하면서 지속적으로 합계를 구하면 시간복잡도가 증가하여 문제의 요구사항을 충족시킬 수 없습니다.
오른쪽 거리는 start, end의 범위에 해당하는 누적합으로 표현할 것입니다.
왼쪽 거리는 총 거리에서 오른쪽 거리를 빼주면 됩니다.
import sys
input = sys.stdin.readline
n = int(input())
arr = [int(input()) for _ in range(n)]
psum = [0 for _ in range(n + 1)]
# 누적합 계산
for i in range(1, n+1):
psum[i] = psum[i - 1] + arr[i - 1]
ans = 0
start, end = 1, 1
while start <= end and end < n+1:
# 오른쪽 거리
right_way = psum[end] - psum[start - 1]
# 왼쪽 거리
left_way = psum[n] - psum[end] + psum[start - 1]
# 오른쪽 거리가 더 크면 end 1증가
if right_way - left_way < 0:
ans = max(ans, right_way)
end += 1
# 그 외에는 start 1 증가
else:
ans = max(ans, left_way)
start += 1
print(ans)
