[백준] 2565번 : 전깃줄

2565번: 전깃줄

# 문제

 

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, <그림 1>과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.

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

 

# 입력

 

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

 

# 출력

 

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

 

# 예시 입력

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

# 예시 출력

3

---

[동적 프로그래밍]

LIS를 응용하는 문제이다. 개인적으로 문제를 어떻게 풀어야 하는 가에 대하여 많은 시행 착오가 있었다. 바이토닉 부분 수열로 푸는 방법으로 계속 시도해보다가 너무 복잡해져서 포기 할 지경에 이르렀었다. 다 엎고 처음부터 다시 쉽게 생각 했더니 풀렸다...

 

전봇대 A와 B가 있을 때, 전깃줄이 곂치지 않고 최대한 많이 걸리는 경우는 각 층 N에 대하여 1-1, 2-2, 3-3, ... (N-1)-(N-1), N-N과 같이 이어져 있을 때 최대가 된다. 그 다음은 1-2, 2-3, 3-4, 4-5, ..., (N-2)-(N-1), (N-1)-N 일 때가 될 것이다. 이처럼 가장 긴 증가하는 부분 수열 문제로 풀면 된다. 하지만 한 가지 더 고려해야 할 점은 전봇대 A의 시점에서 가장 긴 증가하는 부분 수열을 구하고, 전봇대 B의 시점에서도 구한다. 그리고 두 전봇대 A, B가 갖는 가장 긴 증가하는 부분 수열(LIS)의 수가 가장 큰 것을 뽑아서 서로 비교한다.

 

조금 더 직관적으로 보자면 다음과 같이 설명할 수 있다.

전봇대 A의 관점에서 볼 때, 가장 긴 증가하는 부분 수열 vs 가장 긴 감소하는 부분 수열 이라고 할 수 있다. 가장 긴 감소하는 부분 수열은 전봇대 B의 시점에서의 LIS 와 같다. 문제에서 원하는 답은 전깃줄을 최소로 제거해야 전깃줄이 곂치지 않는가? 이므로 n개의 전깃줄이 주어졌다면,

 

n - Math.max(가장 긴 증가하는 부분 수열, 가장 긴 감소하는 부분 수열)

 

라는 답을 갖는다.

 

따라서 입력을 받을 때 배열 2개를 준비했다.

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

라는 입력이 주어졌을 때 A의 관점에서 보면,

 

A전봇대 1층 ------ B전봇대 8층 ==> A[1] = 8

A전봇대 3층 ------ B전봇대 9층 ==> A[3] = 9

...

 

B의 관점에서 보면,

 

B전봇대 8층 ------ A전봇대 1층 ==> B[8] = 1

B전봇대 9층 ------ A전봇대 3층 ==> B[9] = 3

...

 

위와 같이 하나의 입력에 대해 2개의 배열에 값을 저장하도록 한다.

혹시 LIS를 구하는 알고리즘에 대해 가물가물 하다면 이전 포스팅을 참고하면 좋다.

2021/01/16 - [Programming/백준] - [백준] 11053번 : 가장 긴 증가하는 부분 수열

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

---

# Whole Code </> - Java 11

public class Main {

    static final int N = 501;
    static int[] A = new int[N];
    static int[] B = new int[N];

    static int getLIS(int[] arr){

        int tmpIdx = 0, i, j;
        int[] X = new int[N];      //LIS를 구하기 위한 X 테이블 (O(Nlog N)방법)
        int[] result = new int[N]; //LIS가 담길 배열

		//1~n층 까지 전깃줄이 연결되어있지 않을 수 있음
        for(i=1; i<N; i++)
            if(arr[i] != 0){
                X[1] = arr[i];
                result[i] = 1;
                tmpIdx = i; //처음 값이 있는 층의 인덱스 저장
                break;
            }

        for(i=tmpIdx+1; i<N; i++){
        
            if(arr[i] == 0) continue; //다른 층과 연결된 전깃줄이 없으면 pass
            
            for(j=1; X[j] != 0; j++){
				//case 1: arr[i] > X[j]
                if(arr[i] > X[j]){
                
                    result[i] = j + 1;
                    if(X[j+1] == 0) {
                        X[j + 1] = arr[i];
                        break;
                    }
                }
                //case 2: arr[i] < X[j] (arr[i] == X[j]인 경우는 존재하지 않는다)
                else{
                
                    result[i] = j;
                    X[j] = arr[i];
                    break;
                }
            }
        }
        //result배열이 갖는 최대값 반환
        return Arrays.stream(result).max().getAsInt();
    }
    
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt(), idx, value;
        if(x < 1 || x > 100) System.exit(0);

        for(int i=1; i<=x; i++){
        
            idx = sc.nextInt();
            value = sc.nextInt();

            if(idx < 1 || value < 1) System.exit(0);
            if(idx >= N || value >= N) System.exit(0);
            if(A[idx] != 0) System.exit(0);

            A[idx] = value;
            B[value] = idx;
        }
        //A의 가장 긴 증가하는 부분 수열
        //B의 가장 긴 증가하는 부분 수열
        //중에 더 큰 값을 가져와서 전체 전깃줄 수에서 뺄셈
        System.out.printf("%d\n", x - Math.max(getLIS(A), getLIS(B)));
        
        sc.close();
    }
}