[LIS, 이분 탐색] BOJ 2352 반도체 설계 (C++)

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

2352번: 반도체 설계

 

문제 해결 알고리즘

 

LIS알고리즘 (최장 증가 부분 수열 알고리즘)을 써준다. 

 

이 때, $O(n \mathrm{log} n)$ 알고리즘을 사용한다 (이분 탐색).

 

https://kimmessi.tistory.com/191?category=871925 

[알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력

자세한 내용은 위의 링크를 참고

소스 코드

 

#include <bits/stdc++.h>
#define MAX 1000001
using namespace std;
 
int arr[MAX];
int LIS[MAX];
 
int binary_search(int left, int right, int target){
 
    int mid;
 
    while(left < right){
 
        mid = (left + right) / 2;
 
        if(LIS[mid] < target) left = mid + 1;
        else right = mid;
 
    }
 
    return right;
}
 
int main(){
 
    ios::sync_with_stdio(0);
	cin.tie(0);
 
    int N; cin >> N;
 
    for(int i=0;i<N;i++){
        cin >> arr[i];
    }
 
    int j = 0, i = 1;
    LIS[0] = arr[0];
 
    while(i < N){
 
        if(LIS[j] < arr[i]){
            LIS[j+1] = arr[i];
            j++;
        }
        else {
            int idx = binary_search(0, j, arr[i]);
            LIS[idx] = arr[i];
        }
 
        i++;
    }
 
    cout << j+1 << '\n';
 
 
}