Java - [BOJ]2565 - 전깃줄

출처

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

 

문제

 

설치된 전깃줄들이 서로 교차하지 않도록 철거하려고 한다. 가장 최소한으로 전깃줄을  모두 교차되지 않게 하기 위해 철거를 할 때, 철거할 전깃줄의 최소 개수를 구하는 문제이다.

 

풀이

교차되지 않는다? 의 개념을 먼저 정립해보려고 한다. 이 문제에서 '교차하지 않는 것'은 왼쪽 A 전봇대에서 번호가 증가하면 할 수록, 연결된 B 전봇대의 번호도 증가해야 한다는 것이다.

 

즉, A를 기준으로 이전 전봇대와 연결된 전봇대의 번호 < 현재 전봇대와 연결된 전봇대의 번호인 것이 교차하지 않도록 전깃줄을 설치하는 방법이다.

 

A 전봇대 리스트에서, B에 연결된 전봇대의 번호가 증가하는 가장 긴 수열을 찾으면 되는 문제이다. 최장 증가 부분수열 문제로 해결할 수 있다는 소리이다.

 

최장 증가 부분수열의 길이를 찾으면 교차하지 않고 가장 많이 설치할 수 있는 전깃줄의 수를 구할 수 있다. 하지만 문제는, 몇개를 철거하냐고 물어봤기 때문에, (전체 전깃줄) - (가장 많이 설치할 수 있는 전깃줄의 갯수) = 최소로 철거할 전깃줄의 수 를 구하면 된다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[][] arr;
    static int[] dp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        arr = new int[N][2];
        dp = new int[N];



        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr, Comparator.comparingInt(o -> o[0]));

        for (int i = 0; i < N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i][1] > arr[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int result = N - Arrays.stream(dp).max().getAsInt();
        bw.write(result + "\n");

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

}