[2568번] 전깃줄 - 2

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. LIS 알고리즘 :: http://www.crocus.co.kr/583

2. LIS 알고리즘 추적 :: http://www.crocus.co.kr/681

위의 두 링크가 이 문제를 해결하는데 핵심이 된다.

이 문제는 LIS에 해당하는 인덱스 값을 출력해주어야 하는 문제이므로 lis 알고리즘과 lis 추적 알고리즘을 모두 접목해야한다.

자세한 내용은 주석을 통해 달아두었고, 이 문제를 풀기전 lis 알고리즘을 더 알고싶다면

http://www.crocus.co.kr/search/lis 를 참조하면 좋을 것 같다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110

#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <stack> using namespace std;   vector<pair<int, int>> arr; pair<int, int> trace[100003]; int lis[100003]; bool visit[500003];   stack<int> s;   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++)     {         int idx, val;         scanf("%d %d", &idx, &val);           // 인덱스와 값을 넣어준다.         arr.push_back({ idx, val });          // 인덱스가 생긴 부분은 true로 설정         visit[idx] = true;     }       // 인덱스 기준으로 정렬     sort(arr.begin(), arr.end());         // lis 알고리즘을 적용한다.     // 이때 실제 인덱스를 알아야 하기에 lis 추적 알고리즘까지 접목한다.     int pLis = 0, pArr = 1;       lis[pLis] = arr[0].second;     trace[0].first = 0;     trace[0].second = arr[0].first;       vector<int> vc;       while (pArr < n)     {         if (lis[pLis] < arr[pArr].second)         {             lis[++pLis] = arr[pArr].second;               trace[pArr].first = pLis;             trace[pArr].second = arr[pArr].first;         }         else         {             int ans = _lower_bound(0, pLis, arr[pArr].second);             lis[ans - 1] = arr[pArr].second;               trace[pArr].first = ans - 1;             trace[pArr].second = arr[pArr].first;         }           pArr++;     }       printf("%d\n", n - (pLis + 1));       int len = vc.size();     int t = pLis;       // lis 추적 코드     for (int i = n - 1; i >= 0; i--)         if (trace[i].first == t)         {             s.push(trace[i].second);             t--;         }       // 스택에 쌓인 인덱스를 false로 바꿔준다.      while (!s.empty())     {         visit[s.top()] = false;         s.pop();     }       // 정답이 되는 인덱스를 출력     for (int i = 0; i <= 500000; i++)         if (visit[i])             printf("%d\n", i);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus