백준 1365번 꼬인 전깃줄 c++ 풀이

문제

공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.

문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.

임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다.

유스타운 시의 시장 임한수를 도와 잘라내야 할 전선의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 몇 번 전봇대인지를 나타낸다.

출력

전선이 꼬이지 않으려면 최소 몇 개의 전선을 잘라내야 하는 지를 첫째 줄에 출력한다.

예제 입력 1 복사

4
2 3 4 1

예제 출력 1 복사

1

 

 

LIS 문제이다.

꼬인 전깃줄 같은 유형은 최장증가부분수열을 이용하면 된다는 것을 기억할 것

여기에서 전봇대의 개수는 100000이 주어지기 때문에 DP로 LIS를 해결하면 시간초과가 난다고 한다.

따라서 더 효율적인 이진탐색, lower_bound를 활용해야 한다.

 

- c++ 풀이 (참고: https://yhwan.tistory.com/18)

나같은 경우에는 굳이 구현되어 있는 Lower_Bound를 함수로 만들지 않고 만들어져있는 lower_bound를 사용해서 풀었다.

lower_bound(벡터의시작,벡터의끝,비교할 수, comp) - 벡터의 시작 = 첫 번째 비교 이상 값의 위치

#include <bits/stdc++.h>

using namespace std;
vector<int> vt;

int Lower_Bound(int num) {
    int low = 0, high = vt.size() - 1;

    while (low < high) {
        int mid = (low + high) / 2;
        if (vt[mid] >= num)
            high = mid;
        else
            low = mid + 1;
    }
    return high;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, num;
    cin >> n;
    vt.push_back(-1);

    for (int i = 0; i < n; i++) {
        cin >> num;
        if (num > vt[vt.size() - 1])
            vt.push_back(num);
        else
            vt[lower_bound(vt.begin(),vt.end(),num) - vt.begin()] = num;
    }

    cout << n - vt.size() + 1;

    return 0;
}