[1365] 꼬인 전깃줄

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

LIS 문제입니다.

꼬이지 않으려면 내가 연결한 전봇대 보다 번호가 더 큰 전봇대만 선택해야하기 때문입니다.

N^2의 방법으로 해결하려고 했으나,  N이 너무 큽니다.

NlogN으로 해결하는 Lower Bound LIS로 해결해야합니다.

저도 처음해봤는데..

우선 로워바운드는 해당 숫자 이상의 수 중에서 가장 가까운 인덱스를 리턴하는 함수입니다.

(정렬이 되어있을 떄만 가능합니다. 이분 탐색을 응용한 것이기 떄문입니다.)

a배열은 입력들어오는 배열이고

b배열은 정렬된 수가 들어가 있는 배열입니다.

주의할 점은 b배열이 lis의 부분수열이 들어가있는 배열이 아니라는 점입니다.

로워 바운드는 자기보다 작거나 같은 경우 b배열에서 수행해서 자기의 위치를 찾아서 대입합니다.

예를 들어 10 20 30 1 2 3 4 5

라는 수열이 있으면

b배열에 10 20 30 이렇게 들어갈 것입니다.

허나 1을 만나면 10 20 30 이 들어있는 수열에서

로워바운드를 하여 자기 이상의 수 중 가장 인덱스를 찾겠죠.

네 value:10, idx:0 입니다.

그러면 b 배열은 1 20 30으로 바뀌게 됩니다.

또 2를 만나면 자기보다 큰 수를 찾겠죠. 네 20입니다.

1 2 30 으로 바뀌게 됩니다.

3을 만나면

1 2 3으로 바뀌겠죠.

4와 5는 b배열의 3보다 크므로 그냥 삽입하면 됩니다.

b배열은 1 2 3 4 5가 완성이 됩니다.

결국 lis값은 5가 되겠죠.

#include <stdio.h>
 
using namespace std;
int a[(int)1e5];
int b[(int)1e5];
 
int lower_bound(int s, int e, int value) {
    
    while (s <= e) {
        int mid = (s + e) / 2;
 
        if (b[mid] >= value) e = mid - 1;
        else s = mid + 1;
    }
 
    return s;
}
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
        
    int size = 1;
    b[0] = a[0];
    
    for (int i = 1; i < n; i++) {
        if (b[size - 1] < a[i]) {
            b[size] = a[i];
            size++;
            continue;
        }
 
        b[lower_bound(0, size - 1, a[i])] = a[i];
    }
    
    printf("%d", n - size);
 
    return 0;
}