[BOJ/백준] 31410 - 제독 작전

31410번: 제독 작전

---

한 쪽 끝에서 시작해야 불필요한 경로 중복을 없앨 수 있다

 

왼쪽 끝과 오른쪽 끝에서 시작

 

1번째와 N번째를 남겨둘 때는 기준이 달라지기 때문에 기존에 구한 방식과 다르게 따로 구해줘야 한다

---

---

• 제목

제독 작

---

• 조건

시간 제한 : 1 초

메모리 제한 : 1024 MB 

---

• 문제

부대에 미확인 오염 물질이 발생해 위기에 빠졌다! 오염 물질은 부대 내의 수직선 위의 서로 다른 N개의 위치에 발생했으며, 그중 i번째 오염 물질의 오염도는 pi이며 xi 위치에 발생했다. 오염 물질을 정화하기 위해서는 제독병이 오염 물질의 위치까지 이동하여 제독 장비를 사용해 오염도 이상의 제독제를 뿌려야 한다. 이를 위해 제독병은 서둘러 제독 장비에 제독제를 충전하기로 했다.

그러나 제독제를 충전하러 가던 중 실수로 제독 장비를 떨어뜨려 밑부분에 금이 가버렸고, 이 때문에 제독 장비를 사용할 때마다 금이 점점 커져 1분마다 제독 장비를 사용했던 횟수만큼의 제독제가 제독 장비에서 흘러내릴 것이다. 흘러내린 제독제는 더 이상 오염 물질을 정화하는 데 사용할 수 없다.

제독병이 제독을 시작할 수직선 위의 위치는 임의로 정할 수 있으며, 시작할 위치에서 가까운 순서대로 오염 물질을 정화하려 한다. 시작 위치와의 거리가 같은 오염 물질이 있다면, 거리가 같은 오염 물질의 정화 순서는 임의로 정할 수 있다. 제독병은 1분에 1만큼의 거리를 이동할 수 있으며, 제독병이 제독 장비를 사용하면 현재 제독병의 위치에 있는 오염 물질에 제독제를 뿌릴 수 있다. 제독 장비를 한 번 사용할 때 뿌릴 수 있는 제독제의 양에는 제한이 없으며 시간이 소요되지 않는다.

제독병은 미확인 오염 물질을 분석하기 위해 아무 곳이나 한 곳을 남겨 두고 나머지 N-1개의 오염 물질을 제독을 시작할 위치에서 가까운 순서대로 정화하려고 하며, 이를 위해 충전해야 할 제독제의 양을 최소화하고자 한다. 제독병을 위해 금이 간 제독 장비를 사용하여 N-1개의 오염 물질을 정화하기 위해 충전해야 할 최소 제독제의 양을 계산해 주자.

---

• 입력

첫 번째 줄에 오염 물질의 개수를 의미하는 정수 N이 주어진다. (2 ≤ N ≤ 100,000)

이후 N개의 줄에 걸쳐, 각 오염 물질의 위치를 의미하는 정수 xi와 오염도를 의미하는 정수 pi가 공백으로 구분되어 주어진다. (-10^9 ≤ xi ≤ 10^9; 1 ≤ pi ≤ 10^9)$

오염 물질의 위치가 중복되는 입력은 주어지지 않는다.

---

• 출력

금이 간 제독 장비를 사용하여 N-1개의 오염 물질을 정화하기 위해 충전해야 할 최소 제독제의 양을 출력한다.

---

예제 입력1	예제 출력1
3 -3 2 0 1 4 3	6

---

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static class POLUTION{
        int index;
        long level;

        public POLUTION(int index, long level) {
            this.index = index;
            this.level = level;
        }
    }
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        long LSUM = 0, RSUM = 0;
        ArrayList<POLUTION> arr = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int index = Integer.parseInt(st.nextToken());
            long level = Long.parseLong(st.nextToken());
            arr.add(new POLUTION(index, level));
        }
        arr.sort((o1, o2) -> Integer.compare(o1.index, o2.index));
        int MXIDX = arr.get(N - 1).index, MNIDX = arr.get(0).index;
        for (int i = 0; i < N; i++) {
            LSUM += (arr.get(i).index - MNIDX) + arr.get(i).level;
            RSUM += (MXIDX - arr.get(i).index) + arr.get(i).level;
        }
        long answer = Long.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            if(i != 0) answer = Math.min(answer, LSUM - (arr.get(i).index - MNIDX) - arr.get(i).level);
            if(i != N - 1) answer = Math.min(answer, RSUM - (MXIDX - arr.get(i).index) - arr.get(i).level);
        }
        answer = Math.min(answer, LSUM - (long) (N - 1) * (arr.get(1).index - MNIDX) - arr.get(0).level);
        answer = Math.min(answer, LSUM - (MXIDX - MNIDX) - arr.get(N - 1).level);

        answer = Math.min(answer, RSUM - (long) (N - 1) * (MXIDX - arr.get(N - 2).index) - arr.get(N - 1).level);
        answer = Math.min(answer, RSUM - (MXIDX - MNIDX) - arr.get(0).level);

        System.out.println(answer);
    }
}