[BAEKJOON] 2568번 전깃줄 - 2

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

2568번: 전깃줄 - 2

문제조건

1. 두개의 전봇대가 있고, 서로 교차하지않게 전깃줄이 이어지도록 하는 경우일때의 제거해야할 전깃줄 개수와 A전봇대에서의 제거되는 번호
2. 같은 위치에 두개이상의 전깃줄이 연결될 수는 없다.

완전탐색으로 풀려고 시도하면 전깃줄으 개수가 10만개이므로, n^2는 시간초과가 날 것이다.

따라서 어떤 접근법으로 가면 시간을 단축시킬수 있을까 생각해봤다.

이진탐색으로 접근하는 방법인데 다행히도, algorithm헤더 파일에 이를 사용할 수 있도록 함수가 잘 정의되어 있다.

https://chanhuiseok.github.io/posts/algo-55/

알고리즘 - c++ lower_bound, upper_bound 활용하기

lower_bound에 대해서 잘 정리 해주신 글이 있길래 가져왔다.

내가 생각한 방법은 전봇대 B를 기준으로 1번 위치부터 오름차순으로 하나씩 탐색하면서 전봇대 A의 번호가 그 전 B와 연결되어있던 A번호보다 커야한다는 것으로 접근하는 것이다.

ex) 탐색을 진행하다가 꼬여있는 전깃줄을 만났을 경우, lis배열의 이전 최소 인덱스 값이 갱신이되면서 lis배열의 길이가 1씩 늘어날때마다 증가하는 cnt가 증가하지 않게 된다.

A전봇대에서 제거되는 번호는 역으로 탐색하면서 처음만나는 것이 lis배열에 들어 있는 것이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 500001
using namespace std;

int n, a, b, cnt;
int a_point[MAX], lis[MAX], index[MAX];
vector<int> A;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		a_point[b] = a;
	}
	for (int i = 1; i <= MAX; i++) {
		if (a_point[i] == 0) continue;
		//lis에서 정렬유지하며 최소 인덱스 가져옴
		int min = lower_bound(lis, lis + cnt, a_point[i]) - lis;
		//lis크기늘어나면 cnt변수 늘림
		if (min == cnt) cnt++;
		lis[min] = a_point[i];
		index[i] = min + 1;
	}
	cout << n - cnt << '\n';
	for (int i = MAX; i >= 0; i--) {
		if (index[i] == 0) continue;
		//역으로 빼옴
		if (index[i] == cnt) cnt--;
		else A.push_back(a_point[i]);
	}
	sort(A.begin(), A.end());
	for (auto i : A) cout << i << '\n';
}