[JAVA] 백준 (골드5) 2565번 전깃줄

링크

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

---

문제 설명

정답률 47.771%

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.

---

입력 예제

8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

---

출력 예제

3

---

풀이

A와 B사이 전깃줄이 교차하지 않으려면 A와 B가 둘다 정렬되어야 한다. 그래서 각 위치별 LIS를 구한다.

전봇대의 정보는 다음과 같이 2차원 배열에 저장한다. wire[3][0]이면 3번 인덱스의 A 전봇대 정보이다.

int[][] wire = new int[N][2];

우선 A 전봇대를 기준으로 정렬한다.

//A 전봇대를 기준으로 정렬
Arrays.sort(wire, Comparator.comparingInt((int[] o) -> o[0]));

그리고 각 위치의 LIS를 구하여 최댓값을 저장한다. N에서 최댓값을 빼면 답이 된다.

int max = 0;
for (int i = 0; i < N; i++) {
    max = Math.max(max, LIS(i));
}

LIS를 구하는 재귀 함수는 다음과 같이 구현한다. A 전봇대에 대해서 정렬돼 있으므로 B 전봇대의 오름차순되는 수열의 개수를 메모이제이션 배열에 저장한다.

static int LIS(int x) {

    if (dp[x] == null) {
        dp[x] = 1;
        
        //현 위치 다음부터 반복
        for (int i = x + 1; i < N; i++) {
            //현 위치의 A에 연결된 B보다 i번째 B가 뒤에 있을 경우
            if (wire[x][1] < wire[i][1]) {
                dp[x] = Math.max(dp[x], LIS(i) + 1);
            }
        }
    }
    
    return dp[x];
}

코드

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

//백준
public class Main {

    static int[][] wire;
    static Integer[] dp;
    static int N;

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

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        wire = new int[N][2];
        dp = new Integer[N];

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

        //A 전봇대를 기준으로 정렬
        Arrays.sort(wire, Comparator.comparingInt((int[] o) -> o[0]));

        int max = 0;
        for (int i = 0; i < N; i++) {
            max = Math.max(max, LIS(i));
        }

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

    static int LIS(int x) {

        if (dp[x] == null) {
            dp[x] = 1;

            //현 위치 다음부터 반복
            for (int i = x + 1; i < N; i++) {
                //현 위치의 A에 연결된 B보다 i번째 B가 뒤에 있을 경우
                if (wire[x][1] < wire[i][1]) {
                    dp[x] = Math.max(dp[x], LIS(i) + 1);
                }
            }
        }

        return dp[x];
    }
}