[BaekJoon][1365] 꼬인 전깃줄

BAEKJOON ONLINE JUDGE

1365 꼬인 전깃줄

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

LIS 문제

최장 증가 부분 수열의 개수만큼이 잘 연결된 것이고, 나머지를 잘라주면 최소가 된다.

잘은 모르겠지만 직접 예제를 만들어보고 알게됨..

#include <stdio.h>
 
int n;
int size = 1;
int lisArr[100000];
 
void lis(int num)
{
    int s = 0, e = size, middle;
 
    if (lisArr[size - 1] < num) {
        lisArr[size++] = num;
        return;
    }
 
    while (s <= e) {
        middle = (s + e) / 2;
 
        if (lisArr[middle] < num)    s = middle + 1;
        else    e = middle - 1;
    }
 
    lisArr[e + 1] = num;
}
 
int main()
{
    int i;
    int num;
 
    scanf("%d", &n);
    
    scanf("%d", &lisArr[0]);
    for (i = 1; i < n; i++) {
        scanf("%d", &num);
 
        lis(num);
    }
 
    printf("%d\n", n - size);
 
    return 0;
}