1365 꼬인 전깃줄 [JAVA]

문제분석

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

 

X -> Y로 하나의 전선씩 연결되어 있는데, 이 중 최소의 전선을 잘라 전선끼리 겹치는 것이 없게 만드는 것이 목적이다.

 

전선이 서로 겹치지 않기 위해선 최종적으로 남는 각 전선 쌍들이 단조적이여야 한다.

즉, 1-2 / 2-3/ 3-4 이런식으로 서로 겹치지 않아야 한다.

 

이런 순차적인 쌍들의 최댓값을 찾는 것이 최소의 전선을 자르는 방법이기에 이 문제는 LIS(최장 증가 부분수열) 알고리즘으로 접근할 수 있다. N = 10^5 이기에 O(N^2)으론 시간을 맞출 수 없다.

 

 

https://velog.io/@min-ji99/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4LIS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘]가장 긴 증가하는 부분수열(LIS) 알고리즘

LIS에 대해선 위의 설명을 보고 오는게 좋을 것 같다.

 

쉽게 말하면 순차적으로 인덱스를 증가시켜가며 최적의 증가 부분수열을 구해나가는 알고리즘이다.

10 - 20 - 5 - 30 - 8 - 50

이러한 배열이 주어진다면 최장 증가 부분 수열을 구한다면 10-20-30-50이 된다.

 

이걸 LIS로 구한다면

10

10 20

5 20

5 20 30

5 8 30

5 8 30 50

이렇게 되어 최장 증가 부분수열의 길이가 4임을 알 수 있게 된다.

 

유사하게

10 - 20 - 5 - 30 - 6 - 50 - 7 - 8 - 9

을 구해보면

10

 10 20

5 20

5 20 30

5 6 30

5 6 30 50

5 6 7 50

5 6 7 8 9

이렇게 총 길이가 5인 최장 부분 수열을 구할 수 있게 된다.

 

겹치지 않는 전선을 구하는 문제 또한 마찬가지로 인덱스 0번부터 순차적으로 연결된 전신주의 번호 (num)에 대해서 LIS를 구하는 것과 동일하게 해석할 수 있게 된다.

 

코드

import java.util.*;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] lis = new int[n];
        int size = 0;

        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            if(size < 1){
                lis[size++] = num;
                continue;
            }

            if(lis[size-1] < num){
                lis[size++] = num;
            }else{
                int left = 0;
                int right = size;
                int idx = 0;
                while (left<= right){
                    int mid = (left+right)/2;

                    if(num > lis[mid]){
                        left = mid+1;
                    }else{
                        idx = mid;
                        right = mid-1;
                    }
                }
                lis[idx] = num;
            }

        }
        System.out.println(n-size);

    }


}