[백준] #10655 마라톤 1 - 파이썬

문제

농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.

마라톤 코스는 N (3 ≤ N ≤ 100000) 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다. 게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한개를 몰래 건너뛰려 한다. 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.

젖소 박승원이 체크포인트 한개를 건너뛰면서 달릴 수 있다면, 과연 승원이가 달려야 하는 최소 거리는 얼마일까?

참고로, 젖소 마라톤 대회는 서울시내 한복판에서 진행될 예정이기 때문에 거리는 택시 거리(Manhattan Distance)로 계산하려고 한다. 즉, (x1,y1)과 (x2,y2) 점 간의 거리는 |x1-x2| + |y1-y2| 로 표시할 수 있다. (|x|는 절댓값 기호다.)

입력

첫 번째 줄에 체크포인트의 수 N이 주어진다.

이후 N개의 줄에 정수가 두개씩 주어진다. i번째 줄의 첫 번째 정수는 체크포인트 i의 x좌표, 두 번째 정수는 y좌표이다. (-1000 ≤ x, y ≤ 1000)

체크 포인트의 좌표는 겹칠 수도 있다 - 젖소 박승원은 체크포인트를 건너뛸 때 그 번호의 체크포인트만 건너뛰며, 그 점에 있는 모든 체크포인트를 건너뛰지 않는다.

출력

젖소 박승원이 체크포인트 1개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.

예제 입력 1 

4
0 0
8 3
11 -1
10 0

예제 출력 1 

14

---

복기

N = int(input())
coords = [tuple(map(int, input().split())) for _ in range(N)]

# 전체 거리 계산
def manhattan(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

min_dist = int(1e7)

for skip in range(1, N-1): # 처음과 마지막은 생략 불가
    total = 0
    prev = coords[0]
    for i in range(1, N): #거리 구하기
        if i == skip:
            continue
        total += manhattan(prev, coords[i])
        prev = coords[i]
    min_dist = min(min_dist, total)

print(min_dist)

1. 처음에 위와 같이 더해주는 방식으로 했더니 시간초과가 나왔다. 루프를 이중으로 도니 O(N^2)인데 이걸 시간초과 시켜버리네..

2. 더해주는 방식 말고 전체에서 빼주는 방식으로 하면 O(N)으로 시간 초과를 해결했다.

3. 전체 길이에서 원래의 방식으로 계산할때 앞뒤 거리 빼주고, 새롭게 생략할때의 방식으로 거리를 더해줬다. 결국에는 생각을 논리적으로 풀어내는 연습이 필요할거 같다.

---

솔루션

N = int(input())
coords = [tuple(map(int, input().split())) for _ in range(N)]

def manhattan(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])


total_dist = 0
for i in range(1, N):
    total_dist += manhattan(coords[i-1], coords[i])

min_dist = total_dist
for i in range(1, N-1): #i번째 건너뛰기, 처음과 마지막은 건너뛰기 불가
    before = manhattan(coords[i-1], coords[i])
    after = manhattan(coords[i], coords[i+1])
    skip = manhattan(coords[i-1], coords[i+1])

    new_dist = total_dist - (before+after) + skip
    min_dist = min(new_dist, min_dist)


print(min_dist)