BOJ 1365번 꼬인 전깃줄

BOJ : https://www.acmicpc.net/problem/1365

github : https://github.com/junho0956/Algorithm/blob/master/1365/1365/%EC%86%8C%EC%8A%A4.cpp

 

최대로 연결하기 위해서는 최소의 전선을 자르면 된다.

결국 가장 긴 부분수열의 값(lis)을 알고 있다면 전체값에서 빼주면 답이 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int N;
vector<int> dp;
int arr[100001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    dp.push_back(arr[0]);
    int lis = 0;
 
    for (int i = 1; i < N; i++) {
        if (arr[i] > dp[lis]) {
            dp.push_back(arr[i]);
            lis++;
        }
        else {
            int lo = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
            dp[lo] = arr[i];
        }
    }
 
    cout << N-(lis + 1);
    return 0;
}