[BaekJoon] 2300 기지국 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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());
        }
    }
}