[PS] 전깃줄-2 / C++ (백준 2568번)

전깃줄-2 (백준 2568번)

 

 A or B 전봇대 중 하나를 기준으로 선택하여 정렬하고, 나머지 전봇대 배열의 LIS(가장 긴 증가하는 부분 수열)를 구하면 되는 문제. 발상이 생각보다 쉬워서 가장 긴 증가하는 부분 수열 5(백준 14003번)를 풀어봤다면 금방 해결 가능하다.

 

풀이 과정

우선, n이 100,000 이하의 자연수이므로 LIS를 이분 탐색을 사용하여 $O(nlogn)$로 구현하여야 한다.

if (vec[vec.size() - 1] < d[i].first){ .. }

• vector를 만들어 다음 수가 vector에 들어있는 모든 값보다 크다면 수열의 맨 뒤에 추가해 준다.

else{ .. }

• while(st<en){ .. }
  • 그렇지 않다면 이분 탐색으로 해당 수보다 작은 수의 바로 다음 순서를 찾는다.
• vec[en]=d[i].first;
  • 다음 순서로 수열에 끼어든다.
• dp[i]=en+1;
  • 해당 index(i)의 LIS 크기를 저장해 준다.
    • dp[i]: i번째 수를 포함했을 때 LIS(가장 긴 증가하는 부분 수열)의 크기
  • 이 값들을 토대로 역추적하여 삭제할 전깃줄을 구해 출력해 준다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

pair<int, int> d[100'001];
int dp[100'001], dap[100'001];

bool comp(pair<int, int> a, pair<int, int> b) {
	return a.second < b.second;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)scanf("%d %d", &d[i].first, &d[i].second);
	sort(d, d + n, comp);
	vector<int> vec;
	vec.push_back(d[0].first);
	dp[0] = 1;
	for (int i = 1; i < n; i++) {
		if (vec[vec.size() - 1] < d[i].first) {
			vec.push_back(d[i].first);
			dp[i] = vec.size();
		}
		else {
			int st = 0, en = vec.size() - 1, mid;
			while (st < en) {
				mid = (st + en) / 2;
				if (vec[mid] < d[i].first)st = mid + 1;
				else en = mid;
			}
			vec[en] = d[i].first;
			dp[i] = en + 1;
		}
	}
	
	int size = vec.size(), size2 = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (dp[i] != size)dap[size2++] = d[i].first;
		else size--;
	}
	
	sort(dap, dap + size2);
	printf("%d\n", size2);
	for (int i = 0; i < size2; i++)printf("%d\n", dap[i]);
	return 0;
}