[백준] 31410 - 제독 작전

[문제]

---

https://www.acmicpc.net/problem/31410

[풀이]

---

왔던 위치를 되돌아가는 것은 효율적이지 않다.
그렇기 때문에, 정렬을 통해 한 방향으로 이동해야 한다.
가장 작은 x 좌표부터 이동하는 경우와 가장 큰 x 좌표부터 이동하는 경우의 결과 값은 서로 다르다.
2가지 경우로 나눠 $i$번째 오염 물질을 냅두고 가는 식으로 코드를 구성하면 된다.
다만, 마지막에 있는 오염 물질을 냅둔다고 할 때는 식이 좀 달라지므로 따로 구성한다.

문제에서 제독 장비를 사용했던 횟수만큼 이라는 표현이 헷갈렸다.
오염도가 p라면 p번 사용했다고 생각했지만 사실 1번 사용한 것이다..

[코드]

---

import sys
r=sys.stdin.readline

class Polution:
    def __init__(self, x, p):
        self.x = x
        self.p = p

n = int(r())
a = []
for _ in range(n):
    x, p = map(int,r().split())
    a.append(Polution(x, p))

a.sort(key = lambda e : e.x)

usedCount = 1
bottomUp = a[0].p
for i in range(n-1):
    bottomUp += usedCount * (a[i+1].x - a[i].x) + a[i+1].p
    usedCount += 1

usedCount = 1
topDown = a[n-1].p
for i in range(n-1, 0, -1):
    topDown += usedCount * (a[i].x - a[i-1].x) + a[i-1].p
    usedCount += 1

ans = bottomUp
for i in range(n):
    ans = min(ans, bottomUp - a[i].p - (a[n-1].x - a[i].x))

for i in range(n-1, -1, -1):
    ans = min(ans, topDown - a[i].p - (a[i].x - a[0].x))

ans = min(ans, bottomUp - a[-1].p - (n - 1) * (a[-1].x - a[-2].x))
ans = min(ans, topDown - a[0].p - (n - 1) * (a[1].x - a[0].x))

print(ans)