[백준] 2565번 - 전깃줄

 

2565번: 전깃줄

 

 

 

이전에 해결한 백준 11053번 가장 긴 증가하는 부분 수열을 적용할 수 있는 문제이다.

[백준] 11053번 - 가장 긴 증가하는 부분 수열

 

 

 

문제를 읽어보면 두 전봇대 A와 B 사이에 1개 이상의 전깃줄이 연결되어 있는데, 어떠한 전깃줄도 교차하지 않도록 일부 전깃줄을 제거할 때 없애야 하는 전깃줄의 최소 개수를 구하라고 말한다. 두 전깃줄에는 각각 전깃줄이 연결되어 있는 위치 번호를 갖는데 이 위치 번호는 연속적이지 않을 수도 있다. 또한 같은 위치에 두 개 이상의 전깃줄이 연결되는 경우는 없다.

 

이 문제를 해결하기 위해서는 전깃줄이 교차하는 경우에 A, B 상의 전깃줄 위치 값을 비교해봐야 한다.

두 개의 전깃줄이 각각 A(1) - B(8), A(2) - B(2) 와 같이 연결되어 있는 경우 두 전깃줄은 교차한다. 즉, 두 전깃줄이 교차하는 경우는 A전봇대에 연결된 위치의 부등호 방향과 B전봇대에 연결된 위치의 부등호 방향이 달라야 한다.

 

A(1) < A(2)

B(8) > B(2)

 

두 개의 전깃줄이 교차하지 않는 경우에는 이와 반대로 부등호의 방향이 서로 같으면 된다. 예를 들자면 A(1) - B(8), A(10) - B(10) 과 같이 두 전깃줄이 위치해 있다면

A(1) < A(10)

B(8) < B(10)

부등호 방향은 같고 따라서 두 개의 전깃줄을 서로 교차하지 않는다.

 

 

결과적으로, 제거해야 하는 전깃줄의 최소 개수는 A 전봇대 상의 위치 값으로 오름차순 정렬했을 때 B 전봇대에서 위치 값이 증가하는 부분 수열의 최대 길이를 전체 전깃줄 수에서 빼는 것과 같다.

 

전깃줄의 최소 개수 = 전체 전깃줄의 수 - B 전봇대의 위치값의 가장 긴 증가하는 부분수열

 

for (int i=1; i<=N; i++) {
            
    String[] input = br.readLine().split(" ");
    wires[i][0] = Integer.parseInt(input[0]);
    wires[i][1] = Integer.parseInt(input[1]);
}

// 두 전깃줄이 같은 위치에 연결된 경우는 없으므로 단순히 A전봇대 상의 위치에 따라 정렬해준다.
Arrays.sort(wires, (a, b) -> {
    return a[0] - b[0];
});

 

두 전봇대상의 위치를 담기 위해 이중 배열을 사용하였고, 가독성이 좋은 람다표현식을 사용하여 정렬하였다.

 

B전봇대 상에서 증가하는 가장 긴 부분수열을 구하는 것은 이전에 풀이한 11053번 문제와 크게 다르지 않는데 다만, A전봇대가 아닌 B전봇대상의 위치 기준으로 크기비교를 해야 한다.

 

 

 

전체 코드

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

public class Main {
    
    
    static int N;
    static int[][] wires;
    static Integer[] dp;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        dp = new Integer[N+1];
        wires = new int[N+1][2];
        
        dp[1] = 1;
        
        
        for (int i=1; i<=N; i++) {
            
            String[] input = br.readLine().split(" ");
            wires[i][0] = Integer.parseInt(input[0]);
            wires[i][1] = Integer.parseInt(input[1]);
        }
        
        Arrays.sort(wires, (a, b) -> {
            return a[0] - b[0];
        });
        
        
        int max = 0;
        for (int i=1; i<=N; i++)
            max = Math.max(max, LIS(i));
        
        
        System.out.println(N - max);
        
        br.close();
    }
    
    static int LIS (int N) {
        
        if (dp[N] == null) {
            
            dp[N] = 1;
            
            int idx = N - 1;
            
            while (idx > 0) {
                
                if (wires[N][1] > wires[idx][1]) 
                    dp[N] = Math.max(dp[N], LIS(idx) + 1);
                
                idx--;
            }
        }
        
        return dp[N];
    }
}