[백준]#1276 교각 놓기

문제

2010년 노원구에 여러 층으로 이루어진 다리를 놓기로 결정했고 실제 디자인까지 완성하였다. 하지만 당연한 소리일지 모르지만 교각 없이 다리가 공중에 떠있을 수는 없기에 적절히 교각을 설치해야한다.

교각 설치 규칙은 다음과 같다. 다리의 양 끝을 다른 다리 위나 혹은 바닥에 설치해야하고 가능한한 교각의 길이는 최소로 하고 싶다. 단, 다리는 모두 수평으로 놓여있고 다리는 수직으로 세워야한다. 교각이 다른 교각과 교차하면 안된다.

예는 위 그림과 같다. 왼쪽 그림은 디자인된 다리를 표시한 것이고 오른쪽 그림은 교각을 놓은 다리를 표시한 것이다. 그리고 교각의 총 길이는 14가 되는 것을 알 수 있다.

문제는 다리가 주어졌을 때 총 교각의 길이 합을 구하는 것이다.

입력

첫째 줄에 다리의 개수를 나타내는 정수 N(1≤N≤100)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 다리의 위치를 나타내는 세 정수 Y, X1, X2가 주어지는 이는 (X1, Y)부터 (X2, Y)까지 다리가 놓여있다는 의미이다. 모든 좌표는 10000을 넘지않는 자연수이다. 그리고 바닥의 Y좌표는 0이라고 가정한다. (X2 > X1+1)

출력

첫째 줄에 교각 길이의 총 합을 출력한다.

예제 입력 1

3
1 5 10
3 1 5
5 3 7

예제 출력 1

14

풀이

이 문제는 각 입력을 y를 기준으로 정렬한 뒤에 양끝 X의 좌표를 서로 비교해서 교각위에 기둥이 세워지는 지를 판별 후 기둥 높이의 합을 구했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int cnt = 0;
        ArrayList<Pair> list = new ArrayList<>();

        for(int i=0; i<N; i++) {
            String[] input = br.readLine().split(" ");
            int y = Integer.parseInt(input[0]);
            int x1 = Integer.parseInt(input[1]);
            int x2 = Integer.parseInt(input[2]);
            list.add(new Pair(x1, x2-1, y));
        }
        Collections.sort(list);

        for(int i=0; i<N; i++) {
            Pair p = list.get(i);

            for(int j=i-1; j>=-1; j--) {

                if(j==-1) {
                    cnt += p.y;
                    break;
                }
                Pair q = list.get(j);
                if(p.x1>=q.x1 && p.x1<=q.x2) {
                    cnt += (p.y-q.y);
                    break;
                }
            }

            for(int j=i-1; j>=-1; j--) {
                if(j==-1) {
                    cnt += p.y;
                    break;
                }
                Pair q = list.get(j);
                if(p.x2>=q.x1 && p.x2<=q.x2) {
                    cnt += (p.y-q.y);
                    break;
                }
            }
        }

        System.out.println(cnt);
    }

    static class Pair implements Comparable<Pair>{
        int x1;
        int x2;
        int y;

        public Pair(int x1, int x2, int y) {
            this.x1=x1;
            this.x2=x2;
            this.y=y;
        }

        @Override
        public int compareTo(Pair pair) {
            return this.y > pair.y ? 1 : -1;
        }
    }
}