[2565번] 전깃줄

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. LIS :: http://www.crocus.co.kr/583

LIS 문제중 가장 기본적인 문제이다.

알고리즘 과정은 다음과 같다.

입력 받기 -> 순번대로 정렬하기 -> lis 구하기 

-> 이때 lis 과정에 들어가는 상황에 cnt++(lower_bound를 쓴다는 의미가 전깃줄이 꼬였다는 의미)

-> cnt 출력

Crocus 블로그에서 lis로 검색하면 다양한 유사한 문제를 확인하고 풀이를 볼 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int lis[501];
pii arr[501];
 
int _lower_bound(int start, int end, int target)
{
    int mid;
 
    while (start < end)
    {
        mid = (start + end) / 2;
 
        if (lis[mid] < target)
            start = mid + 1;
        else
            end = mid;
    }
    return end + 1;
}
 
int main()
{
    int n;
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d %d", &arr[i].first, &arr[i].second);
    
    sort(arr, arr + n);
 
    int pLis = 0, pArr = 1, cnt = 0;
 
    lis[pLis] = arr[0].second;
 
    while (pArr < n)
    {
        if (lis[pLis] < arr[pArr].second)
            lis[++pLis] = arr[pArr].second;
 
        else
        {
            int ans = _lower_bound(0, pLis, arr[pArr].second);
            lis[ans - 1] = arr[pArr].second;
            cnt++;
        }
 
        pArr++;
    }
 
    printf("%d", cnt);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

sort를 내림차순으로하면 lds로도 풀 수 있다.

 
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int _lower_bound(int start, int end, int target, vector<int> lds)
{
    int mid;
 
    while (start < end)
    {
        mid = (start + end) / 2;
 
        if (lds[mid] > target)
            start = mid + 1;
        else
            end = mid;
    }
    return end + 1;
}
 
bool comp(const pii &a, const pii &b)
{
    if (a.first == b.first)
        return a.second < b.second;
    return a.first > b.first;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    vector<pii> vc;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
 
        vc.push_back({ a,b });
    }
 
    sort(vc.begin(), vc.end(), comp);
 
    vector<int> lds;
    lds.push_back(vc[0].second);
    int pVc = 1;
    while (pVc < vc.size())
    {
        if (lds.back() > vc[pVc].second)
            lds.push_back(vc[pVc].second);
        else
        {
            int pos = _lower_bound(0, lds.size() - 1, vc[pVc].second, lds);
            lds[pos - 1] = vc[pVc].second;
        }
        pVc++;
    }
 
    cout << n - lds.size() << endl;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>