My Profile

김형훈

안녕하세요.
김형훈입니다.

백준 2565 전깃줄

백준 2565 전깃줄

2022년 11월 27일

2022년 11월 27일

cpp, 이분 탐색

문제

문제

풀이

풀이

두 전깃줄 (A1,B1), (A2,B2)에 대해 만약 A1이 A2보다 작고, B1이 B2보다 작다면 두 선은 교차하지 않는다.

여기서 잠시 최장 증가 수열의 개념에 대해 알아보자.

  • 정수 i , j에 대해 i < j이면 s[i] < s[j]이다.

여기서 i 를 A전봇대의 번호, s[i]를 B전봇대의 번호로 생각하면, 해당 문제는 A전봇대의 전깃줄들을 오름차순으로 탐색할 때, B의 값이 증가하는 형태를 띄는 순열의 최대값을 구하는 문제라는것을 알 수 있다.

코드

코드

#include <bits/stdc++.h>

using namespace std;

int n;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    vector<pair<int,int>> arr;
    for(int i=0; i<n; ++i){
        int a,b; cin >> a >> b;
        arr.push_back({a,b});
    }
    sort(arr.begin(),arr.end());
    vector<int> lis;
    for(int i=0; i<n; ++i){
        if(lis.empty() || lis.back() < arr[i].second) lis.push_back(arr[i].second);
        else{
            auto index = lower_bound(lis.begin(),lis.end(),arr[i].second);
            *index = arr[i].second;
        }
    }
    cout << n - lis.size();
}

결과

결과

Copyright © 2024 Hyunghoon Kim