[백준 1365] 꼬인 전깃줄 (C++)

문제 링크: www.acmicpc.net/problem/1365

1365번: 꼬인 전깃줄

1. 주의할 점

- LIS(가장 증가하는 부분수열)에 대해 알고 있어야 한다

 

2. 구현

- 모든 수에 대한 입력을 Arr[] 배열에 받는다

- DP[idx] 배열 통해 가장 긴 증가하는 부분 수열을 나타낼 때, idx번째로 작은 수를 DP[idx]에 저장한다

- 만약 새로 비교하는 값(Arr[i])가 DP[] 배열의 가장 마지막 원소(DP[idx])보다 크면, DP배열에 새로 추가한다.

- 반대로 작은 값이라면, 이분탐색을 통해 DP[]의 0~idx번째 원소중에 갈아 끼울 수 있는 수가 있는지 확인한다

#include <iostream>
using namespace std;
int arr[100000];
int dp[100000];

int b_search(int r, int v){
    int l=0,mid,result=0;
    while(l<=r){
        mid = l + (r-l)/2;
        if(dp[mid]>=v){
            r = mid-1;
            result = mid;
        }
        else
            l = mid+1;
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num,idx=0;
    cin>>num;
    for(int i=0;i<num;i++)
        cin >> arr[i];
    dp[0] = arr[0];
    for(int i=1;i<num;i++){
        if(arr[i]>dp[idx]){
            dp[++idx] = arr[i];
        }
        else{
            int val = b_search(idx,arr[i]);
            dp[val] = arr[i];
        }
    }
    cout << num-(idx+1);
    return 0;
}