BOJ 2565번 전깃줄

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

github : https://github.com/junho0956/Algorithm/blob/master/2565/2565/%EC%86%8C%EC%8A%A4.cpp

 

오름차순 정렬이 되어있어야하고, lis 알고리즘에서 lower_bound의 의미를 알아보자면

ex) 만약 현재 lis의 마지막 second가 5이고 현재 걸려있는 줄의 second가 4이면 꼬여있는 상태가 됨을 의미하고,

     만약 현재 lis의 마지막 second가 5이고 현재 걸려있는 줄의 second가 6이면 꼬이지 않은 상태가 됨을 의미한다.

 

꼬일때 lower_bound -> lis의 길이를 찾는 문제이다

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<pair<int, int> > v;
int lis[501];
int n, f, s, cnt, L;
 
int _lower_bound(int start, int end, int key) {
    int mid;
    while (start < end) {
        mid = (start + end) / 2;
        if (lis[mid] < key)
            start = mid + 1;
        else
            end = mid;
    }
    return end + 1;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &f, &s);
        v.push_back(make_pair(f, s));
    }
    sort(v.begin(), v.end());
    lis[0] = v[0].second;
    for (int i = 1; i < n; i++) {
        if (lis[L] < v[i].second) {
            lis[++L] = v[i].second;
        }
        else {
            int ans = _lower_bound(0, L, v[i].second);
            lis[ans - 1] = v[i].second;
            cnt++;
        }
    }
    printf("%d", cnt);
}

 

복습 20.02.10