https://www.acmicpc.net/problem/2300
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int buildingNum;
static List<Building> buildings;
static void input() {
Reader scanner = new Reader();
buildingNum = scanner.nextInt();
buildings = new ArrayList<>();
for (int cnt = 0; cnt < buildingNum; cnt++) {
buildings.add(new Building(scanner.nextInt(), scanner.nextInt()));
}
}
/*
* 인접한 기지국들이 같은 통신범위에 들어갈테니 x좌표를 기준으로 오름차순으로 정렬하여 최소 설치비용을 구한다
* 기지국을 설치할 때, 특정 위치의 건물이 어떤 기지국의 통신범위에 포함되어야 하는지 정해야 한다
* 그러므로 각 건물을 각 통신범위에 넣어보며 최소 설치비용을 구한다
* 이때 이전에 구해놓은 최소 설치비용을 이용하여 해당 통신범위에 현재 건물을 넣어보며 최소 설치비용을 구한다
* - dp[building] = min(dp[building], dp[1 ~ building] + max(1 ~ building번째 빌딩의 y좌표 * 2, building번째 빌딩의 x좌표 - 1 ~ building번째 빌딩의 x좌표))
* - dp[building] = building번째 건물까지 기지국을 설치하였을 때 최소 설치비용
* - 1번 빌딩부터 현재 빌딩까지를 순회하며 이전에 구해놓은 1번 빌딩부터 현재 순회 중인 빌딩까지의 최소 설치비용을 이용한다
* 1. 현재 순회 중인 빌딩부터 building번째 빌딩을 하나로 묶고 그 기지국의 설치비용을 구한다
* 2. 현재 순회 중인 빌딩 바로 전까지의 최소 설치비용을 dp 배열을 통해 알 수 있으니 이를 더해준다
*
* - 1번 빌딩부터 현재 순회 중인 빌딩 바로 전까지의 최소 설치비용은 dp 배열을 통해 알 수 있으니
* - 현재 순회 중인 빌딩부터 building번째 빌딩까지를 하나로 묶어본다
* - 이때 필요한 설치비용은 두 빌딩 사이의 거리가 될 것이다(즉, x좌표 차이)
* - 그런데 현재 순회 중인 빌딩의 y좌표 * 2 값이 두 빌딩 사이의 거리보다 멀다면 현재 순회 중인 빌딩을 포함시키기 위해 y좌표 * 2 값으로 통신범위를 설정해야 한다
* - 그러므로 두 값 중 더 큰 값을 통신범위로 잡는다
* - 이렇게 구한 통신범위에 1번 빌딩부터 현재 순회 중인 빌딩 바로 전까지의 최소 설치비용을 더하면 최소 설치비용이 된다
*/
static void solution() {
Collections.sort(buildings);
int[] dp = new int[buildingNum + 1];
for (int basisIdx = 1; basisIdx <= buildingNum; basisIdx++) {
int dist = 0;
dp[basisIdx] = Integer.MAX_VALUE;
for (int idx = basisIdx; idx >= 1; idx--) {
dist = Math.max(dist, Math.abs(buildings.get(idx - 1).y));
dp[basisIdx] = Math.min(dp[basisIdx],
dp[idx - 1] + Math.max(2 * dist, buildings.get(basisIdx - 1).x - buildings.get(idx - 1).x));
}
}
System.out.println(dp[buildingNum]);
}
static class Building implements Comparable<Building> {
int x;
int y;
public Building(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Building o) {
if (x != o.x) {
return x - o.x;
}
return y - o.y;
}
}
public static void main(String[] args) {
input();
solution();
}
static class Reader {
BufferedReader br;
StringTokenizer st;
public Reader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}