백준 - 반도체 설계(2352) / LIS + 이분탐색

오늘 풀어볼 문제는 ⭐반도체 설계라는 문제이다.

1. 문제 요약

• 서로 다른 포트를 연결하고자 한다.
• 이떄 포트간 선이 겹치지 않게 놓을 수 있는 최대 갯수를 구하라.
  

2. 입출력

[입력]

• n개의 정수(1 ≤ n ≤ 40,000)
• 차례로 1번 포트부터, n개까지 연결되어야 하는 반대쪽 포트 번호가 주어진다.

[출력]

• 포트 선이 겹치지 않게 최대 연결 개수를 출력한다.

3. 알고리즘

• 특정 조건을 만족하는 최대의 개수 구하기 (=LIS)
• 개수가 무려 40,000이므로, 일반적인 LIS O(n^2)가 아닌, 이분탐색을 활용한 O(LogN2)로 풀어야 한다.

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int[] binary = new int[n];

        st = new StringTokenizer(br.readLine());
        int len = 0;
        for (int i = 0; i < n; i++) {
            int value = Integer.parseInt(st.nextToken());

            // lower_bound
            int l = 0, r = len;
            while (l < r) {
                int m = (l + r) >>> 1;
                if(binary[m] >= value)
                    r = m;
                else
                    l = m + 1;
            }
            binary[l] = value;
            if (l == len) len++; //⭐핵심코드!!⭐
        }

        System.out.println(len);
    }
}