[백준] 2118 - 두 개의 탑

1. 문제

2118번: 두 개의 탑

2. 개요

거리가 주어진 원 둘레의 지점 두 곳에 탑을 세울 때 그 두 탑의 최대거리를 구하는 문제.

3. 코드 및 추가내용

import sys

N = int(sys.stdin.readline())

dists = []
ans = 0
tmp = 0
for i in range(N):
    tmp += int(sys.stdin.readline())
    dists.append(tmp)

peri = dists[-1]
for i in range(N):
    for j in range(i+1, N):
        ans = max(ans, min(dists[j] - dists[i], peri - (dists[j] - dists[i])))

print(ans)

시간초과가 떴다.

모든 경우 탐색 + 대소비교 2번을 하는게 문제인듯 싶었다

import sys

N = int(sys.stdin.readline())

dists = []
ans = 0
tmp = 0
for i in range(N):
    tmp += int(sys.stdin.readline())
    dists.append(tmp)

peri = dists[-1]
for i in range(N):
    for j in range(i+1, N):
        if dists[j] - dists[i] >= peri / 2.0:
            ans = max(ans, peri - (dists[j] - dists[i]))
            break
        ans = max(ans, dists[j] - dists[i])

print(ans)

한 구간이 반지름 이상의 거리일 경우 건너뛰는 조건을 추가해서 어떻게 꾸역꾸역 넘겼다.

채점 결과들을 보니 속도가 독보적으로 느리더라…