[백준][Java] 2565 - 전깃줄

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

2565번: 전깃줄

난이도 : G5

유형 : LIS, DP

 

비슷한 문제

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

7578번: 공장

---

문제 풀이

세그먼트 트리로도 풀리지만 LIS 풀이가 더 쉬워서 LIS로 풀었다.

필자는 최장증가부분수열(LIS) 개념을 알고 있어서 쉽게 접근할 수 있었다.

문제에선 최소의 갯수를 물어보지만 역발상으로 최대의 개수에 초점에 맞추면 풀이가 더 쉬워진다.

 

설치된 전선을 왼쪽 번호 기준으로 정렬한 후

앞에서부터 순차적으로 탐색하면서 자신보다 오른쪽 번호가 작은 전선을 카운팅 하며 dp테이블을 갱신하면 된다.

 

예시)

예시 케이스입력을 정렬한 상태

1 - 8       ->  dp[1] = 1, 1개(본인)만 설치가능

2 - 2      ->  dp[2] = 1, 이전의 전선의 오른쪽(8)이 자신보다 크기 때문에 본인만 설치가능, 1개

3 - 9      ->  dp[3] = 2, 본인과 첫 번째 줄 가능(dp[1] + 1) 혹은 본인과 두 번째 줄 가능(dp[2] + 1)

4 - 1       ->  dp[4] = 1, 1개(본인)만 설치가능

6 - 4      ->  dp[5] = 2, 본인과 두 번째 줄 가능(dp[2] + 1) 혹은 본인과 네 번째 줄 가능(dp[4 + 1)

7 - 6.     ->  dp[6] = 3, dp[5] + 1 

9 - 7.     ->. dp[7] = 4, dp[6] + 1

10 - 10.  ->   dp[8] = 5, dp[7] + 1

 

이렇게 현재 전선의 오른쪽 값보다 작은 이전의 전선들의 dp에 +1 하여 최댓값을 갱신해 나가면 된다.

---

코드

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

public class Main {

    class Line implements Comparable<Line> {
        int left;
        int right;

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

        @Override
        public int compareTo(Line o) {
            return this.left - o.left;
        }
    }

    private int N;
    private Line[] lines;
    private int[] dp;

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        lines = new Line[N];
        dp = new int[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            lines[i] = new Line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(lines);

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

        System.out.println(N - max);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}