[BOJ] 2352. 반도체 설계

LIS를 이용하여 푸는 문제였다.

예를 들어 1-4 를 연결시켰다고 가정해보면 이제 다음 부터 연결할 수 있는 거는 좌측의 4보다 큰 값을 가진 선만 연결할 수 있게 된다. 따라서 이 문제는 자동적으로 최장 증가 수열의 길이를 찾는 문제가 된다. LIS를 만들 수 있는 방법은 크게 두가지 dp와 lower_bound가 있다. dp의 경우 n^2의 시간복잡도를 가지고, lower_bound는 nlogn의 시간복잡도를 가지는 이문제의 경우 n의 최대값이 40000이기 때문에 dp말고 lower_bound 기법을 적용하여 풀 수 있다.

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_2352_반도체설계 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        int N = Integer.parseInt(br.readLine());
        int[] LIS = new int[N + 1];        //LIS[i]는 i의 길이의 최장 증가 수열에서 가지는 마지막 원소
        int[] arr = new int[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        int cur = 0;
        for (int i = 0; i < N; i++) {
            if (LIS[cur] < arr[i]) {
                cur += 1;
                LIS[cur] = arr[i];
            } else {
                int lowerBound = lowerBound(LIS, cur, arr[i]);
                LIS[lowerBound] = arr[i];
            }
        }
 
        System.out.println(cur);
    }
 
    static int lowerBound(int[] LIS, int cur, int value) {
        int startIndex = 0;
        int endIndex = cur;
 
        while (startIndex < endIndex) {
            int midIndex = (startIndex + endIndex) / 2;
 
            if (LIS[midIndex] < value) {
                startIndex = midIndex + 1;
            } else {
                endIndex = midIndex;
            }
        }
 
        return endIndex;
    }
}