[백준 1365] 꼬인 전깃줄

 

 LIS 문제다. 문제를 잘 해석해 보면, 꼬임이 발생하지 않는 경우는 왼쪽 전봇대와 연결된 오른쪽 전봇대의 번호가 계속해서 증가하는 형태로 나타날 때임을 알 수 있다. 따라서 LIS의 길이를 구하고, 전봇대의 개수에서 그만큼을 빼준다면 잘라내야 하는 전선의 수가 될 것이다.

 LIS 자체를 출력할 필요도 없기 때문에, 역추적을 위한 추가 처리 등이 전혀 필요하지 않다. 이런 간단한 형태의 LIS 문제에 대한 설명은 이전에 풀었던 아래 문제를 참조하면 좋을 것 같다. 거의 같은 유형.

https://winterry.tistory.com/102

[백준 12015] 가장 긴 증가하는 부분 수열 2

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> arr(n);
    for(int i=0; i<n; i++) {
        cin >> arr[i];
    }

    vector<int> lis;
    lis.push_back(arr[0]);

    for(int i=1; i<n; i++) {
        if(arr[i]>lis[lis.size()-1]) {
            lis.push_back(arr[i]);
        } else {
            *lower_bound(lis.begin(), lis.end(), arr[i]) = arr[i];
        }
    }

    cout << n-lis.size();
}