백준 2565번 전깃줄

문제 링크입니다: https://www.acmicpc.net/problem/2565

백준 2352번 반도체 설계(https://jaimemin.tistory.com/488)와 유사한 문제였습니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 500 + 1;

 

int N;

pair<int, int> connect[MAX];

int cache[MAX];

 

int LIS(void)

{

        int idx = 0;

        int length = 0;

        cache[idx] = connect[0].second;

 

        for(int i=1; i<N; i++)

        {

                 if (cache[idx] < connect[i].second)

                         cache[++idx] = connect[i].second;

                 //줄이 꼬였다

                 else

                 {

                         int idx2 = lower_bound(cache, cache + idx, connect[i].second) - cache;

                         cache[idx2] = connect[i].second;

                         length++;

                 }

        }

        return length;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> connect[i].first >> connect[i].second;

 

        sort(connect, connect + N);

 

        cout << LIS() << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~