[백준 / 골드5] 2170 선 긋기 (Java)

문제 보기

사용한 것

• 선분의 총 길이를 구하기 위한 그리디

풀이 방법

• 그리디로 풀이하기 위해 좌표들을 x 좌표 오름차순 먼저, x 좌표가 같으면 y 좌표로 오름차순 정렬한다.
• 오름차순 정렬된 배열을 돌면서 이전 좌표와 현재 좌표로 그리디 풀이한다.
• x 좌표로 오름차순 정렬되어 있기 때문에 가능한 경우의 수는 다음과 같다.
  • 현재 선분이 이전 선분에 포함
  • 현재 선분이 이전 선분에 겹침
  • 현재 선분이 이전 선분에 겹치지 않음
• 위 세 경우의 수를 생각해서 구현한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] points = new int[n][2];
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            points[i] = new int[]{x, y};
        }

        // 그리디를 위한 정렬 (x 오름차순 먼저, y 오름차순)
        Arrays.sort(points, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });

        // 그리디
        int lastX = points[0][0];
        int lastY = points[0][1];
        int totalLen = lastY - lastX;
        for (int i = 1; i < n; i++) {
            int curX = points[i][0];
            int curY = points[i][1];

            if (curX >= lastX && curY <= lastY) {
                continue;
            } else if (curX >= lastY) {
                totalLen += curY - curX;
            } else {
                totalLen += curY - lastY;
            }

            lastX = curX;
            lastY = curY;
        }

        System.out.println(totalLen);
    }
}