-
백준 2568번 : 전깃줄-2 (C++)알고리즘/BOJ 2021. 7. 2. 21:04
문제 : https://www.acmicpc.net/problem/2568
2568번: 전깃줄 - 2
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결
www.acmicpc.net
전깃줄이 서로 겹치지 않게 하기 위해 제거해야 하는 전깃줄의 최소 개수와 해당 전기 줄들을 출력해야 하는 문제다. 위 문제는 가장긴부분수열 문제로 만약 해당 문제를 풀지 않았다면 먼저 아래 문제부터 풀어보도록하자
https://www.acmicpc.net/problem/14003
전깃줄 정보를 입력받은 뒤 A 위치에 따라 정렬시킨다음 B 위치 값에 따른 가장긴부분수열을 구하면 된다. 왜냐하면 전깃줄이 서로 엉키지 않기 위해서는 A전봇대에서 아래에 위치노드의 B값이 위에서 나오는 노드의 B값보면 작으면 교점이 생기기 때문이다.
가장긴부분수열을 구하는 것은 어렵지않다. 1 -> N 값으로 넘어가면서 만약 부분수열을 쌓아주는데 만약 부분수열의 마지막 값보다 작으면 부분수열의 중간값중 해당되는 위치와 값을 바꿔주면 최적의 부분수열을 얻을 수 있다. 단 해당되는 위치를 찾을때 선형 탐색으로 찾으면 O(n^2) 으로 시간초과가 뜬다. 그러므로 O(nlogn) 이 될수있도록 이진탐색으로 위치를 찾아야 한다.
for(int i=1; i<x.size(); i++){ int next = x[i].second; if(ans.back() < next){ ans.push_back(next); } else{ int left = 0; int right = ans.size() - 1; while (left < right) { int mid = (left+right)/2; if(ans[mid] <next){ left = mid+1; } else{ right = mid; } } ans[left] = next; }그 다음 지워야하는 전깃줄을 출력해야하는데 ans 벡터에 있는 값을 가지고 출력을 하면 오답이 뜰 것이다. ans 벡터에는 값 대소에 따른 위치를 파악하는거기 때문에 ans는 정답의 크기는 보장하지만 정답의 배열 값은 보장하지 않는다. 그래서 각 원소의 index를 기록해둘필요가 있다. 기록해둔 index를 뒤에서부터 추적하면 가장긴부분수열의 원소값들을 추적할수 있다.
#include <iostream> #include <vector> #include <algorithm> #include<cstring> #include <cmath> #include <set> #include <queue> #include <unordered_map> #include <deque> #include <string> typedef long long ll; using namespace std; using namespace std; int n; vector<pair<int, int>> x; vector<int> ans,idx; int main(){ cin.tie(NULL); ios::sync_with_stdio(false); cin >> n; for(int i=0; i<n; i++){ int a, b; cin >> a >> b; x.push_back(make_pair(a,b)); } sort(x.begin(), x.end()); ans.push_back(x.front().second); idx.push_back(0); for(int i=1; i<x.size(); i++){ int next = x[i].second; if(ans.back() < next){ ans.push_back(next); idx.push_back(ans.size()-1); } else{ int left = 0; int right = ans.size() - 1; while (left < right) { int mid = (left+right)/2; if(ans[mid] <next){ left = mid+1; } else{ right = mid; } } ans[left] = next; idx.push_back(left); } } cout << x.size() - ans.size() << "\n"; int now = ans.size()-1; vector<int> sibal; for(int i = idx.size()-1; i>=0; i--){ if(now == idx[i]){ now--; } else{ sibal.push_back(x[i].first); } } sort(sibal.begin(), sibal.end()); for(int i : sibal) cout << i << "\n"; }'알고리즘 > BOJ' 카테고리의 다른 글
백준 2473번 : 세 용액 (C++) (0) 2021.07.13 백준 1744번 : 수 묶기 (C++) (0) 2021.07.07 백준 1799번 : 비숍 (C++) (0) 2021.07.02 백준 11505번 : 구간 곱 구하기 (C++) (0) 2021.07.01 백준 1062번 : 가르침 (C++) (0) 2021.07.01