[Python/파이썬] 백준 2118번 두 개의 탑

2118번: 두 개의 탑

 

문제

1번부터 N번까지의 지점이 있다. 각각의 지점들은 차례로, 그리고 원형으로 연결되어 있다. 이 지점들 중 두 곳에 두 개의 탑을 세우려고 하는데, 두 탑의 거리가 최대가 되도록 만들려고 한다.

지점들이 원형으로 연결되어 있기 때문에, 두 지점 사이에는 시계방향과 반시계방향의 두 경로가 존재한다. 두 지점 사이의 거리를 잴 때에는, 이러한 값들 중에서 더 작은 값을 거리로 한다.

연결되어 있는 두 지점 사이의 거리가 주어졌을 때, 두 탑의 거리의 최댓값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 지점의 개수 N(2 ≤ N ≤ 50,000)이 주어진다. 다음 N개의 줄에는 차례로 두 지점 사이의 거리가 양의 정수로 주어진다. 전체 거리의 총 합은 1,000,000,000을 넘지 않는다.

출력

첫째 줄에 답을 출력한다.

코드

import sys
input = sys.stdin.readline

n = int(input())
point = []
acc = [0] * (n+1)   # 누적 합
for i in range(n):
    point.append(int(input()))
    acc[i+1] = acc[i] + point[i]

total = acc[n]    # 모든 지점 사이의 거리들의 합

ans = 0
for i in range(1, n+1):
    start, end = i, n
    while start <= end:
        mid = (start+end) // 2
        length1 = acc[mid] - acc[i-1]
        length2 = total - length1
        if length1 < length2:
            start = mid + 1
        else:
            end = mid - 1
        ans = max(ans, min(length1, length2))
print(ans)

 

acc 배열에 입력으로 주어진 연결되어 있는 두 지점 사이의 거리들의 누적합을 구해놓고 이를 이분탐색하여 답을 구한다.

원형으로 지점들이 연결되어 있으므로 시계방향과 반시계 방향의 거리의 합(total)은 항상 같다.

이분탐색을 이용하여 시계방향과 반시계방향의 길이 차가 최소가 되는 순간을 찾으면 된다. 탑1은 i, 탑2는 mid 위치에 있다고 생각하면 된다.