2568

초등부의 전깃줄 문제에서 한발 나아간 문제.

기본적으로 LIS를 이용해서 풀 수 있는 것은 똑같지만 Input의 개수가 1000배이상 증가해서

O(N*N) 기본탐색 알고리즘을 사용하면 시간초과가 날게 틀림없으므로

좀 더 효율적인 자료구조를 활용해 속도를 높일 필요가 있었다.

나는 priority queue를 이용해서 풀었는데

priority queue는 이전 까지 탐색했던 line중에서 LIS값이 높은 순위로 저장되어있다.

priority queue는 pair<int, int>로 이루어져 있는데 pq가 pair.first를 통해서 정렬한다는 점을 알면 구현하기 편리하다

d값, value값, idx값 총 세가지 값이 필요한데 나는 pair.second로 idx값을 넣어서 value값은 넣지 않고 idx값을 통해서 참조 할 수 있게 만들었다.

#include<iostream> #include<cstdio> #include<queue> #include<map> using namespace std; const int MAX= 500005; int d[MAX]; int bfo[MAX]; int line[MAX]; bool exist[MAX]; int main() { priority_queue<pair<int,int>> pq; int n, idx, val, max_idx=0; scanf("%d", &n); for(int clk=0; clk<n; clk++) { scanf("%d %d", &idx, &val); line[idx]=val; d[idx]=1; exist[idx]=true; max_idx = max(max_idx, idx); } for(int piv=0; piv<=max_idx; piv++) { if(line[piv]!=0) { priority_queue<pair<int,int>> tpq; pair<int,int> tmp; tpq=pq; tmp.first=d[piv]; tmp.second=piv; while(!tpq.empty()) { if(line[tpq.top().second] < line[piv]) { d[piv] = tpq.top().first+1; tmp.first = d[piv]; tmp.second = piv; bfo[piv] = tpq.top().second; break; } tpq.pop(); } pq.push(tmp); } } printf("%d\n", n-pq.top().first); int next=pq.top().second; while(next!=0) { exist[next]=false; next=bfo[next]; } for(int i=1; i<=max_idx; i++) if(exist[i]) printf("%d\n", i); return 0; }