[백준] 2352번 : 반도체 설계

🤔 문제분석

📝 문제요약

n개의 포트를 연결 할때 겹치지 않는 상태로 연결해야한다.

겹치지 않는 상태로 연결을 하기 위해서는 오른쪽의 포트가 오름차순으로 정렬 되어있어야한다. 따라서 증가하는 가장 긴 부분수열을 찾으면 문제는 해결 된다.

🎯 필요한 개념

• 이분탐색
• 증가하는 가장 긴 부분수열

✅ 알고리즘

1. 하나씩 입력받는다.
2. 입력받은 데이터에 현재 수열중 가장 작은 인덱스를 찾아낸다.
   1. 만약 인덱스가 없다면 수열에 추가한다.
   2. 인덱스가 존재한다면 해당 인덱스의 값을 입력받은 데이터로 치환한다.
3. 부분수열의 길이를 출력한다.

💻 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;
int n;
vector<int> ls;

int bisect(const int v)
{
    int start = 0;
    int end = ls.size() - 1;
    int answer = -1;
    while(start <= end)
    {
        int mid = (start + end) / 2;

        if(ls[mid] >= v)
        {
            answer = mid;
            end = mid - 1;
        }
        else
        {
            start = mid + 1;
        }
    }

    return answer;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    int temp;
    for(int i = 0; i < n; i ++)
    {
        cin >> temp;
        int idx = bisect(temp);
        if(idx == -1)
        {
            ls.push_back(temp);
        }
        else
        {
            ls[idx] = temp;
        }
    }
    
    cout << ls.size();
}