백준 1365번 꼬인 전깃줄 - C++(cpp) 풀이

---

 

1. 줄이 꼬이지 않으려면 연결된 오른쪽 전봇대들의 번호가 오름차순이어야 한다.
2. 잘라내는 전깃줄을 최소로 하려면, 남아있는 전깃줄을 최대로 하면 된다.
3. 가장 긴 증가하는 부분 수열의 길이만큼 남기는 것이 최대이다.

 

1. 줄이 꼬이지 않으려면 연결된 오른쪽 전봇대들의 번호가 오름차순이어야 한다.

 왼쪽 i번 전봇대와 연결된 오른쪽 전봇대의 번호를 A[i]라고 하면, i < j일 때 A[i] > A[j]이면 줄이 꼬이게 된다. 반대로 A[i] < A[j]이면 줄이 꼬이지 않는다. 따라서 줄이 꼬이지 않기 위해서는 연결된 오른쪽 전봇대들의 번호가 오름차순이어야 한다. 

 

2. 잘라내는 전깃줄을 최소로 하려면, 남아있는 전깃줄을 최대로 하면 된다.

 잘라내는 전깃줄을 최소로 하여 꼬인 부분이 없게 만들어야 한다. 즉, 꼬인 부분이 없으면서 남아있는 전깃줄이 최대가 되도록 만들어야 한다.

 

3. 가장 긴 증가하는 부분 수열의 길이만큼 남기는 것이 최대이다.

 1, 2번을 종합하면 가장 긴 증가하는 부분 수열의 길이를 구하는 문제임을 알 수 있다. N = 10^6이므로 O(NlogN)의 LIS 알고리즘을 사용하여 해결할 수 있다.

반응형

---

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 100001;

int N;
int A[MAX];
vector<int> v;

int lower_bound(int x) {
    int lo = 0, hi = v.size();
    
    while (lo < hi) {
        int mid = (lo+hi) / 2;
        if (v[mid] < x) lo = mid+1;
        else hi = mid;
    }
    
    return lo;
}

int LIS() {
    v.push_back(0);
    
    for (int i=0; i<N; i++) {
        if (v.back() < A[i]) {
            v.push_back(A[i]);
        }
        else {
            int lb = lower_bound(A[i]);
            v[lb] = A[i];
        }
    }
    
    return v.size() - 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) cin >> A[i];
    
    cout << N - LIS();

    return 0;
}