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

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

 

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

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

---

1.  아이디어

 

다이나믹 프로그래밍 중 LIS 알고리즘으로 해결할 수 있다.

---

2. 문제풀이

 

전깃줄을 A 전봇대를 기준으로 위에서부터 번호를 매겼을 때 전깃줄이 교차하지 않는 상태는 전깃줄의 순서가 커질수록 B 전봇대에서의 위치가 같이 커져야 한다. 이를 활용해 A 전봇대 위치를 기준으로 정렬한 후 B 전봇대에서의 위치에 대한 LIS를 구하면 이 값이 서로 교차되지 않고 연결될 수 있는 최대 전깃줄의 수이다.문제는 없애야할 전깃줄의 최소 개수를 구해야하므로 처음 주어진 전깃줄의 수에서 LIS의 크기를 뻬주면 된다.

---

3. 코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        int[][] map = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            map[i][0] = Integer.parseInt(st.nextToken());
            map[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(map, ((o1, o2) -> Integer.compare(o1[0], o2[0])));

        int[] dp = new int[N];
        Arrays.fill(dp, 1);
        int min = N;

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

        System.out.println(min);
    }
}

---

4. 후기