[백준/Baekjoon] 2568 전깃줄-2 C++ :: LIS(nlogn)

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

2568번: 전깃줄 - 2

---

1. Logic

처음 보면 무슨 문제가 싶지만 문제를 읽으면서 예제를 보면 LIS문제인것을 알 수 있다. 문제 푸는 로직을 나열해보자면

1. 입력을 받은 수들을 vector에 pair로 저장을 하고 A를 기준으로 오름차순 정렬한다.

2. lis vector의 back값과 계속 비교하여 LIS를 이루는 값이 들어오면 lis에 넣어주고 cnt를 올려준다. 혹은 탐색값이 lis의 back보다 더 작은 수가 나오게 되면 입력받은 값에 대한 lower_bound의 인덱스값을 찾고 해당하는 LIS vector의 인덱스에 넣어준다.

3. 경로 추적 : trace배열을 뒤에서부터 확인하면서 lis를 이루는 숫자는 tr--해주고 건너뛰고 LIS를 이루는 숫자가 아닌경우 경로를 저장하는 tra배열에 pushback 해준다.

 

시간복잡도가 O(NlogN)인 문제의 풀이과정을 자세하게 알고싶으면 내가 풀이하고 작성한 아래의 블로그를 참고하면 좋을 듯 하다! 

https://go2gym365.tistory.com/81

[백준/Baekjoon] 12015 가장 긴 증가하는 부분 수열 2 C++ :: LIS

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;
//LIS의 길이
int cnt = 0;

//lis를 저장하는 배열(여기에 저장된 수들을 항상 LIS를 이루는 숫자는 아님)
vector<int> lis;
//입력받는 배열
vector<pair<int, int>> input;
//역추적
int trace[100001];

int binarySearch(int key) {
    int start = 0;
    int end = lis.size() - 1;
    int mid;

    while(start < end) {
        mid = (start + end) / 2;
        if(key > lis[mid]) {
            start = mid + 1;
        }
        else {
            end = mid;
        }
    }

    return end;
}

void solve() {
    for(int i = 0; i < n; i++) {
        if(lis.empty() || lis.back() < input[i].second) {
            trace[i] = cnt;
            lis.push_back(input[i].second);
            cnt++;
        }
        else {
            //lis의 인덱스임
            int idx = binarySearch(input[i].second);
            lis[idx] = input[i].second;
            trace[i] = idx;
        }
    }
}

void print() {
	//LIS의 길이를 제외한 갯수
    cout << n - cnt << "\n";
    int tr = cnt - 1;
    vector<int> tra;
    for(int i = n - 1; i >= 0; i--) {
        if(trace[i] == tr) {
            tr--;
        }
        else {
        	//lis가 아닌 수는 제외
            tra.push_back(input[i].first);
        }
    }
    for(int i = tra.size() - 1; i >= 0; i--) {
        cout << tra[i] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n;

    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        m[b] = a;
        input.push_back({a, b});
    }

    sort(input.begin(), input.end());

    solve();
    print();
}

---

3. Feedback

이분탐색을 사용하여 LIS를 구하는 기본적인 문제였지만 경로추적을 할 때 이전문제와 동일하게 약간 해맸다..

 

 

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐