BOJ 10655 - 마라톤1 (Python)

S3, 구현

풀이

아무생각없이 O(N²)의 완탐으로 풀었다.
당연하게도 시간초과 발생

# 시간초과 코드
from sys import stdin
n = int(stdin.readline())
checks = []

res = int(1e9)

for _ in range(n):
    x, y = map(int, stdin.readline().split())
    checks.append([x, y])

for i in range(1, n-1):
    val = 0
    tmp = checks[:i] + checks[i + 1:]
    for j in range(len(tmp)-1):
        val += abs(tmp[j][0] - tmp[j + 1][0]) + abs(tmp[j][1] - tmp[j + 1][1])
    res = min(res, val)

print(res)

그래서 총 움직이는 거리에서 하나를 제외한 가장 부분이 긴 거리를 빼기로 했다.

from sys import stdin
n = int(stdin.readline())
checks = []

for _ in range(n):
    x, y = map(int, stdin.readline().split())
    checks.append([x, y])

total = 0

for i in range(n-1):
    total += abs(checks[i][0] - checks[i+1][0]) + abs(checks[i][1] - checks[i+1][1])

maxDis = 0
for i in range(1, n-1):
    prev_to_mid = abs(checks[i][0]-checks[i-1][0])+abs(checks[i][1]-checks[i-1][1])
    mid_to_end = abs(checks[i+1][0]-checks[i][0])+abs(checks[i+1][1]-checks[i][1])
    prev_to_end = abs(checks[i+1][0]-checks[i-1][0])+abs(checks[i+1][1]-checks[i-1][1])
    val = prev_to_mid + mid_to_end - prev_to_end
    maxDis = max(maxDis, val)

print(total-maxDis)

• 이러면 O(N²) → O(N)으로 줄여 시간초과를 해결할 수 있다.