[C/C++] 백준 #2565 전깃줄(가장 긴 증가하는 부분수열)

이번 문제는 백준내에서도 아주 자주 나오는 가장 긴 증가하는 부분수열(LIS; Longest Incremental Sub-sequence) 문제입니다.

 

power lines

 

전깃줄이 꼬이지 않게 배열하기 위해서 몇개의 전깃줄을 없애야 하는 문제입니다.

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

2565번: 전깃줄

 

그동안 제가 작성했던 가장 긴 증가하는 부분 수열 문제들을 모아두면 다음과 같습니다.

 

https://sdev.tistory.com/1384

 

https://sdev.tistory.com/1047

 

https://sdev.tistory.com/577

 

꼬인 전깃줄 문제는 이 문제와 거의 같은 문제입니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2565 - Electric lines
//        - by Aubrey Choi
//        - created at 2019-11-22
//------------------------------------------------
#include <stdio.h>
#include <algorithm>
struct Line { int a, b; };
bool cmp(Line &a, Line &b) { return a.a<b.a; }
int main()
{
    int n, i, s[100], p=1; Line v[100];
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d%d",&v[i].a, &v[i].b);
    std::sort(v,v+n,cmp);
    for(s[0]=v[0].b,i=1;i<n;i++)
    {
        if(v[i].b>s[p-1]) { s[p++]=v[i].b; continue; }
        auto it = std::lower_bound(s,s+p,v[i].b);
        *it = v[i].b;
    }
    printf("%d\n", n-p);
}