[BOJ 2352] 반도체 설계(이분탐색)

이 문제는 증가하는 수열의 최장길이를 구하는 문제와 동일하다.

 

 

 

1 2 3 4 5 6

4 2 6 1 3 5

 

 

 

n번 포트끼리 겹치지 않는 방식을 살펴보면, 최장길이를 구하는 방식과 동일함을 알 수 있다.

 

 

 

 

주의할점은, N * N 시간복잡도가 아닌 이분 탐색(N * log N)을 이용해야 한다.

 

 

이분 탐색에 대한 이해를 돕기 위한 개념들을 좀 적어보자면,

 

 

 

 

이분 탐색을 위해 새로 선언된 벡터는 항상 정렬된 상태를 유지하게 된다. 

 

 

 

 

왜냐하면, lower_bound도 함수의 정렬을 방해하지 않는다. lower_bound의 역할은 최장길이를 찾을 수 있도록 기존의 벡터의 원소들을 변경시킨다.

 

 

 

 

벡터의 원소들을 변경시켜도, 현재 최장길이엔 변함이 없다. 다만, 미래에 최장길이를 찾을 수 있는 가능성을 만들어준다.

 

 

 

 

해설코드(C++).

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int N, val;
int result = 0;
vector<int> v;
 
int main() {
    cin >> N;
    v.push_back(-1);
    
    for(int i = 1; i <= N; i++){
        cin >> val;
        
        if(v.back() < val){
            v.push_back(val);
            result += 1;
        }
        else
        {
            auto it = lower_bound(v.begin(), v.end(), val);
            *it = val;
        }
    }
 
    cout << v.size() - 1 << endl;
    return 0;
}