취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2565번 문제인 전깃줄이다.
문제는 아래 링크를 확인하자.

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

서로 교차하지 않는 전깃줄의 최대 개수는 한쪽 전봇대를 기준으로 1번서부터 연결된 전깃줄의 끝의 LIS와 같다는 점을 확인하자.

글쓴이는 LIS를 세그먼트 트리를 이용하여 구했다.

아래는 제출한 소스코드이다.

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

int seg[1025];

int update(int L, int R, int qI, int qVal, int sI) {
	if (R < qI || qI < L) return seg[sI];
	if (L == R) return seg[sI] = qVal;
	return seg[sI] = max(update(L, (L + R) / 2, qI, qVal, sI * 2), update((L + R) / 2 + 1, R, qI, qVal, sI * 2 + 1));
}

int rangemax(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return max(rangemax(L, (L + R) / 2, qL, qR, sI * 2), rangemax((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

vector<pair<int, int>> queries;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		queries.push_back({ x,y });
	}
	sort(queries.begin(), queries.end());

	for (auto q : queries) {
		int lis = rangemax(1, 500, 1, q.second, 1) + 1;
		update(1, 500, q.second, lis, 1);
	}

	cout << N - seg[1];
}