BOJ#2565 전깃줄

BOJ#2565 전깃줄

* 문제

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

Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2007 > 초등부 4번

* 풀이

문제 : 전깃줄이 교차하지 않기 위해 없애야 하는 전깃줄의 최소 개수를 구하시오.

문제에서 표시된 위 지문과 같이 전깃줄을 '제거'하는 관점에서 접근하게 되면 문제를 풀기 어려워지게 됩니다.

전깃줄을 하나씩 '제거'하면서 최소한 몇개를 제거해야 하는지 생각하는 것 보다,

전깃줄을 하나씩 '추가'하면서 최대한 몇개까지 겹치지 않고 추가할 수 있는지 생각해 봅시다.

* 전깃줄이 겹치지 않을 조건

 : A를 기준으로 정렬했을 때, B가 순차적으로 나열되어 있으면 된다.

주어진 입력을 A 기준으로 정렬해보면 LIS의 형태가 보인다.

(LIS : http://stack07142.tistory.com/56)

1 8 

2 2 

3 9 

4 1 

6 4 

7 6

9 7 

10 10 

LIS는 [2 4 6 7 10] 또는 [1 4 6 7 10]으로 길이가 5이다. 따라서 8 - 5 = 3.

즉 최소 3개를 제거하면 전깃줄이 교차하지 않게 된다.

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%232565_ElectricWire/src

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * BOJ#2565 전깃줄
 * https://www.acmicpc.net/problem/2565
 */

public class Main {

    public static void main(String[] args) throws IOException {

        int N; // 전깃줄의 갯수
        Wire[] list;

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine().trim());

        list = new Wire[N];

        for (int i = 0; i < N; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine().trim());

            list[i] = new Wire(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        // solve
        Arrays.sort(list);

        int[] tailTable = new int[N];
        int length;

        // 초기값
        tailTable[0] = list[0].b;
        length = 1;

        for (int i = 1; i < N; i++) {

            int candidate = list[i].b;

            if (candidate < tailTable[0]) {

                tailTable[0] = candidate;
            } else if (candidate > tailTable[length - 1]) {

                tailTable[length++] = candidate;
            } else {

                int idx = Arrays.binarySearch(tailTable, 0, length, candidate);
                idx = idx < 0 ? -idx - 1 : idx;

                tailTable[idx] = candidate;
            }
        }

        bw.write(String.valueOf(N - length));
        bw.flush();

        bw.close();
        br.close();
    }
}

class Wire implements Comparable<Wire> {

    int a;
    int b;

    Wire(int a, int b) {

        this.a = a;
        this.b = b;
    }

    @Override
    public int compareTo(Wire o) {

        return this.a < o.a ? -1 : 1;
    }
}