[Algorithm]Baekjoon 2352번 :: 반도체 설계

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
 
int n;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    vector<int> lis;
 
    for (int i = 0; i < n; ++i)
    {
        int num;
        
        cin >> num;
 
        if (lis.size() == 0)
        {
            lis.push_back(num);
            continue;
        }
 
        int lowerIndex = lower_bound(lis.begin(), lis.end(), num) - lis.begin();
 
        if (lowerIndex == lis.size())
        {
            lis.push_back(num);
        }
        else
        {
            lis[lowerIndex] = num;
        }
    }
 
    cout << lis.size();
}
 
 

 

골드2인데 정답률이 높은 이유는.. 비슷한 유형의 문제들이 꽤 있기때문이라 생각한다.

이문제에선 반도체인데 다른문제에선 전봇대였나?? 로 바뀌어서 비슷한 문제가 있었어서 바로 풀었다.

결국 최대 오름차순길이를 구하는 문제로, 교차하지않기위해서는 이전에 선택했던것보다 높은것을 선택해야하기 때문이다.