[백준 c++] 2565 전깃줄

문제

https://www.acmicpc.net/problem/2565
두 전봇대 A와 B 사이에 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 문제다.

풀이

전깃줄이 겹치지 않으려면 A전봇대를 오름차순 정렬했을 때 B전봇대도 오름차순으로 정렬되어 있어야한다. 그래서 pair vector로 입력받은 후 오름차순으로 정렬해줬다.

다음 그림에서 교차되지 않은 전깃줄의 개수는 3개고
이는 곧 (오름차순 정렬된 B전봇대 배열에서의) 가장 긴 증가하는 부분 수열의 길이인 것이다🙀

최적의 위치를 찾기 위한 배열 vector lis

0. B전봇대를 순회
1. 벡터가 비어있거나 현재 값이 마지막 원소보다 큰 값이면 삽입
2. 아니면 lower_bound를 이용해서 값 변경

출력은 지워야하는 전깃줄의 개수이므로 전체 전깃줄 개수(n) - lis.size()

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector<int> lis;
int main()
{
    cin >> n;
    vector<pair<int, int>> v(n);
    
    for (int i = 0; i < n; i++)
        cin >> v[i].first >> v[i].second;
        
    sort(v.begin(), v.end());

    for (int i = 0; i < n; i++)
    {
        if (lis.empty())
            lis.push_back(v[i].second);
        else
        {
            if (lis[lis.size() - 1] < v[i].second)
                lis.push_back(v[i].second);
            else
                *lower_bound(lis.begin(), lis.end(), v[i].second) = v[i].second;
        }
    }
    cout << n - lis.size() << "\n";
    return 0;
}