[백준] 1365번: 꼬인 전깃줄 - C++

문제 출처:https://www.acmicpc.net/problem/1365

---

문제

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

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

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

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

입력

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

출력

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

이런 문제를 처음 풀어본다면 대체 어떻게 접근해야 하는지 감이 안잡힐 수도 있지만  

몇가지 예시를 들어 문제를 풀어보면 한 가지 패턴을 찾을 수 있습니다. 

입력: 7    3    1    2    0    6    8    9    4    10 

이런 전선 입력이 주어졌다면 여기서 꼬이지 않고 전선을 잘라내는 방법은 

7    3    1    2    0    6    8    9    4    10

빨간색으로 칠한 전선을 잘라내는 것 입니다. 전선을 잘라내고 남아있는 전선(1, 2, 6, 8, 9, 10)을 보면 한 가지 패턴이 있는데 

바로 '증가하는 수열' 이라는 겁니다.

따라서 이 문제는 어떤 임의의 수열이 주어졌을 때, 이 수열에서 몇 개의 수를 제거하여 만들 수 있는 부분수열 중 오름차순으

로 정렬된 가장 긴 수열을 찾는 최장 증가 부분 수열(LIS : Longest Increasing Subsequence)알고리즘을 이용하여 푸는 문제

입니다.

이 LIS알고리즘은 O(n^2)과 O(n log n)의 시간이 걸리는 알고리즘이 각각 있지만 이 문제에선 최대 입력이 100,000이므로 

O(n^2)의 알고리즘을 사용하면 시간초과에 걸립니다. 따라서 저는 O(n log n)의 알고리즘을 소개하고 문제를 풀겠습니다.

O(n log n)의 알고리즘에선 이진탐색을 약간 변형한 알고리즘인 Lower bound를 사용하게 됩니다. 

입력값은 위에 예시로 든 수열을 그대로 사용하겠습니다.

입력: 7    3    1    2    0    6    8    9    4    10

1. 벡터를 하나 만들어 줍니다.

2. 수열을 처음부터 검사하는데 현재 검사하는 수를 A라고 했을때 벡터의 마지막 요소를 비교하여 

    - A 가 벡터의 마지막 요소보다 크면 벡터의 마지막에 추가해준다.

   - A 가 벡터의 마지막 요소보다 작으면 Lower bound하여 나온 index위치의 값과 교환해준다.

3. 최종적으로 만들어진 벡터의 길이 N이 최장 증가 수열의 길이가 된다.

그림으로 하나하나 표현하면 아래와 같습니다.

이렇게 최종적으로 만들어진 수열(0, 2, 4, 8, 9, 10)의 길이가 LIS의 길이가 됩니다.

문제의 정답인 잘라야 하는 전선의 수는 주어진 (n - LIS의 길이)를 하면 나오게 됩니다.

단 이 문제에서는 LIS의 요소를 요구하지는 않았는데 위에서 구해진 수열이 LIS를 나타내는건 아닙니다.

직접 눈으로 확인해봐도 수열 7    3    1    2    0    6    8    9    4    10 의 최장 증가 수열은 

1    2    6    8    9    10 이지만 LIS알고리즘을 통하여 구해진 수열은 0    2    4    8    9    10 입니다.

따라서 LIS의 요소까지 구하려면 추가적인 작업을 해야하지만 그 방법은 다음 문제에서 알아 보도록 하겠습니다.

전체 코드입니다.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <ctime>
#include <string.h>
#include <limits>
 
using namespace std;
 
int Lower_Bound(vector<int> vt, 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(void)
{
    int n, num;
    scanf("%d", &n);
    vector<int> vt;
    vt.push_back(-1);
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        if (num > vt[vt.size()-1])
            vt.push_back(num);
        else 
            vt[Lower_Bound(vt, num)] = num;
    }
    printf("%d", n - vt.size() + 1);
 
    return 0;
}