[백준 2352] 반도체 설계 (C++)

문제 링크: www.acmicpc.net/problem/2352

2352번: 반도체 설계

1. 주의할 점

- LIS 알고리즘에 대해 알고 있어야 한다

- 이분탐색을 통한 LIS를 수행한다

 

2. 구현

- 모든 수를 Arr[] 배열에 담는다

- DP[idx] 배열에 가장 긴 증가하는 부분수열 중에서 idx번째에 위치한 수를 저장한다

- DP[0] = Arr[0]을 담은 후, 1번째 index부터 탐색을 시작한다

- 만약 DP[Idx]보다 Arr[i]가 크다면, 가장 긴 증가하는 부분수열의 길이가 1 증가했으므로 DP[++Idx] = Arr[i]가 성립한다

- 크지 않다면, 이전에 구했던 긴 증가하는 부분수열중에서 수정이 가능한 부분이 있는지 이분탐색을 통해서 찾는다. 범위는 DP[] 배열의 인덱스 0~ Idx까지

- 초기에 DP[0]에 값을 할당했지만 Index는 0이므로, 결과로는 Index+1을 출력한다

#include <iostream>
using namespace std;
int arr[40000];
int dp[40000];

int b_search(int r, int val){
    int l=0,mid,result=r;
    while(l<=r){
        mid = l+(r-l)/2;
        if(dp[mid]>=val){
            result = mid;
            r = mid-1;
        }
        else
            l = mid+1;
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num,idx=0;
    cin>>num;
    for(int i=0;i<num;i++)
        cin >> arr[i];
    dp[0]=arr[0];
    for(int i=1;i<num;i++){
        if(arr[i]>dp[idx]){
            dp[++idx]=arr[i];
        }
        else{
            int val = b_search(idx,arr[i]);
            dp[val]=arr[i];
        }
    }
    cout << idx+1;
    return 0;
}