[백준] 1365 꼬인 전깃줄

잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다. → 전선을 잘라내는데 모두 동일한 비용이 든다. 그리고 전선이 꼬여있지 않으려면 왼쪽 전봇대를 커지는 차례로, 연결된 오른쪽 전봇대의 숫자를 확인했을 때 앞서 나온 전봇대 숫자보다 커야 꼬여있지 않은 상태가 된다. 즉, 연결된 오른쪽 전봇대 숫자를 수열로 보고 이 수열에서 가장 길이가 긴 증가하는 부분수열을 구했을 때 가장 적은 비용으로 전봇대의 전선을 자르는 꼴이 된다.

가장 길이가 긴 증가하는 부분수열의 길이를 구하기 → 부분수열에 있는 원소를 구하는 것이 아닌 길이만 구하면 되는 문제이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, x;
vector<int> arr;

int main()
{
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> x;
        if (arr.empty() || arr.back() < x) {
            arr.push_back(x);
        }
        else {
            arr[lower_bound(arr.begin(), arr.end(), x)-arr.begin()] = x;
        }
    }
    cout << N - arr.size();
    return 0;
}