백준 2352 - 반도체 설계

문제

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

풀이

연결선이 꼬이지 않게 최대 연결 수를 구하려면 결국 주어진 포트 번호중 가장 긴 오름차순 부분 수열을 구해야 한다. 따라서 LIS 알고리즘을 적용해 풀이할 수 있다.

로직의 시간복잡도는 LIS 알고리즘의 $O(NlogN)$으로 수렴하고, $N=40,000$인 최악의 경우에도 무난히 제한 조건 2초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        int[] arr = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        List<Integer> lis = new ArrayList<>();
        for (int num : arr) {
            int index = Collections.binarySearch(lis, num);
            if (index < 0) index = -(index + 1);

            if (index == lis.size()) {
                lis.add(num);
            } else {
                lis.set(index, num);
            }
        }

        System.out.println(lis.size());
        br.close();
    }
}

결과