백준 2568번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	플래티넘 5

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

---

풀이

 밀린 문제 정리하기... 라고 하기엔 너무 최근에 푼 문제라서 밀렸다고 해야하나 싶다. 여행가기전에 풀었던 마지막 문제이자, 알고리즘에 대한 이해도를 높여야겠다고 절실하게 느낀 문제이다.

 

 문제 자체는 이전에 풀었던 전깃줄 - 1(2565번, https://codejin.tistory.com/316)과 다를게 없는 문제이다. 다만 포트의 개수와 번호가 천배 늘어났으며, 출력해야할 답이 늘어났다 정도이다. 없애야할 전깃줄의 개수를 구하는건 전깃줄 - 1과 다를게 없지만, 잘라야 하는 전깃줄의 데이터도 출력해야한다.

 

 결국 우리는 실제 LIS를 구해야한다는 것인데, 문제는 LIS 알고리즘으로는 실제 LIS를 구할 수 없다는 것이다. LIS알고리즘으로 구할 수 있는 것은 LIS의 길이이지, 실제 LIS가 아니기 때문이다. 따라서 LIS를 구현할때는, LIS의 길이를 구하기 위한 LIS가 될 수 있는 후보군을  저장하는 배열과, i번째 원소를 사용했을 때의 LIS의 길이 데이터를 저장하는 dp 배열을 같이 사용하는 것이 일반적...일 것이다. 아마도 그럴 것이다. 실제로 LIS를 구하는 방법은 이 dp 배열을 통해 구한다. 역시 이것도 나중에 정리할 것이다. 내가 만족스러운 이해도에 도달한 그때 말이다. 간단히 설명하면 dp 테이블을 뒤에서부터 순회하며 LIS의 길이에 맞는 원소를 아무거나 하나 고르고, 해당 길이를 줄여나가며 찾는다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
#define endl '\n'
using namespace std;
using pii = pair<int,int>;

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() {
	vector<int> lis_length(1), dp(n);
	deque<int> lis;

	for(int i = 0; i < n; i++) {
		int con = wire[i].second;

		if(lis_length[lis_length.size() - 1] < con) {
			lis_length.push_back(con);
			dp[i] = lis_length.size() - 1;
		}
		else {
			int idx = lower_bound(ALL(lis_length), con) - lis_length.begin();
			lis_length[idx] = con;
			dp[i] = idx;
		}
	}

	int len = lis_length.size() - 1;
	cout << n - len << endl;

	for(int i = n - 1; i >= 0 && len; --i) {
		if (dp[i] == len) {
			--len;
			lis.push_front(wire[i].second);
		}
	}

	for(auto& [a, b] : wire) {
		auto p = lower_bound(ALL(lis), b);
		if (*p != b) {
			cout << a << endl;
		}
	}
}

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