BOJ) 전깃줄 (2565 번)

전깃줄

2565번: 전깃줄

 

A와 B 두 전봇대가 주어지고, 두 전봇대를 잇는 전기줄의 정보가 주어진다.

이 때, 전깃줄이 교차하는 경우를 없애기 위해 전깃줄을 제거해야 하는데, 가장 최소한의 전깃줄을 제거해서 교차하는 경우가 되게 만드는 문제다.

교차하는 가장 최소한의 전깃줄을 제거한다는 것은 전체 전깃줄에서 가장 올바르게 연결된 전깃줄 수를 빼주는 것과 성립한다.

 

전체 전깃줄 (n) - 가장 많이 올바르게 연결된 전깃줄 = 불필요하게 교차된 전깃줄의 최소값

 

여기서 가장 많이 올바르게 연결된 전깃줄은 왼쪽 전봇대가 연결되는 오른쪽 전봇대 번호를 기준으로 가장 긴 증가하는 부분수열(LIS)를 구해주면 된다.

증가하는 부분 수열은 전깃줄이 교차하지 않는다는 의미이고, 가장 긴 증가하는 부분 수열은 가장 올바르게 많이 연결된 전깃줄의 수를 의미하기 때문이다.

 

코드

 

package remindBOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class ElectricWire_2565 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Wire[] wires = new Wire[n];
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            wires[i] = new Wire(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        br.close();
        Arrays.sort(wires);
        solution(wires, n);
    }

    private static void solution(Wire[] wires, int n) {
        int[] dp = new int[n];
        int maxLine = 0;

        for(int i=0; i<n; i++) {
            dp[i] =1;
            for(int j=0; j<i; j++) {
                if(wires[i].right > wires[j].right) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            maxLine = Math.max(dp[i], maxLine);
        }

        System.out.println((n-maxLine));
    }

    static class Wire implements Comparable<Wire> {
        int left, right;

        public Wire(int left, int right) {
            this.left = left;
            this.right = right;
        }

        @Override
        public int compareTo(Wire w) {
            return this.left - w.left;
        }
    }
}