백준 2565번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	골드 5

사진을 클릭하면 문제로 이동합니다.

---

풀이

 밀린 문제 정리하기. LIS이다.

 

 저번 반도체 설계(2352번, https://codejin.tistory.com/315)에서 한번 더 문제를 꼬아버렸다. 이번에는 LIS를 적용하기 위한 수열도 만들어야 한다. 말은 거창하지만 별거 없으니 한번 출발해보자.

 

 해당 문제 여기 전깃줄이 꼬이지 않도록(교차하지 않도록) 하는 최대 개수를 구하는 문제이다. 그와 동시에 A에서 B로 연결해야하는 전선의 포트 정보를 같이 준다. 2352번을 해당문제에 적용시켜보면 A -> B로 연결되는 정보가 단순했다. A의 정보는 1부터 n까지 오름차순이고, B로 연결될 때 뒤죽박죽이었기 때문이다. 그렇기에 그 문제는 바로 B에서 LIS를 찾으면 되는 문제였다. 하지만 이 문제는 A도 뒤죽박죽이다. 우선 해당 문제를 풀기 위해 A를 기준으로 전선의 정보를 오름차순 정렬을 하면 2352번 문제와 동일해진다. 이제 B를 기준으로 LIS를 찾는다면 전깃줄이 교차하지 않으면서, 최대로 연결할 수 있는 갯수를 찾을 수 있다. 해당 문제는 이 갯수를 만들기 위해 몇개의 전깃줄을 없애야 하는지이기 때문에 전체 개수에서 lis의 길이를 빼면 그것이 답이다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;

int n;
vector<pair<int,int>> wire;

void input() {
	cin >> n;
	wire.resize(n);
	for(auto& [a, b] : wire) cin >> a >> b;
	sort(ALL(wire));
}

void sol() {
	int con;
	vector<int> lis{0}, dp(n, 0);

	for(int i = 0; i < n; i++) {
		con = wire[i].second;
		if(lis[lis.size() - 1] < con) {
			lis.push_back(con);
			dp[i] = lis.size() - 1;
		}
		else {
			int idx = lower_bound(ALL(lis), con) - lis.begin();
			lis[idx] = con;
			dp[i] = idx;
		}
	}
	cout << n - lis.size() + 1;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	input();
	sol();
}