[P5] 백준 2568번 전깃줄 - 2 C++ LIS, 이분 탐색

리뷰

 

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

lower_bound를 통해 가장 긴 증가하는 부분 수열을 구하고 경로 역추적을 해줘야 하는 문제

4달 전엔 경로 역추적에 대한 지식이 없어 틀렸으나 다시금 보니 문제 풀이가 가능했다.

 

골드 전깃줄 문제에 비해 티어가 훨씬 높으며 경로 역추적을 모른다면 어떻게 풀어야 할지 모르겠다.

[G5] 백준 2565번 전깃줄 C++ LIS, 이분 탐색

[G5] 백준 2565번 전깃줄 C++ LIS, 이분 탐색

 

 

전역 변수

• n : 전깃줄의 개수를 저장할 변수
• lst : 전깃줄의 정보를 저장하기 위한 pair<int, int>타입의 벡터
• lis : 가장 긴 증가하는 부분 수열을 구하기 위한 정수형 벡터

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 전깃줄 정보를 입력 받아 lst에 저장해 준다.
2. lst를 오름차순으로 정렬해 주고, lis의 각 인덱스를 저장할 정수형 벡터 index를 n크기로 초기화 한다.
3. n개의 전깃줄 정보를 순회하며 현재 전깃줄을 pair<int, int>타입의 변수 cur로 파싱한다.
4. lower_bound 메서드를 통해 lis에 cur의 second값 이상인 요소를 찾아 이터레이터로 it으로 반환한다.
5. 현재 전깃줄의 index를 lis의 몇번째 인덱스 요소인지 저장해 준다.
6. it이 lis의 end라면 lis에 현재 B전깃줄이 위치한 값을 추가해 준다.
7. end가 아니라면 it에 저장된 값을 현재 B전깃줄이 위치한 값을 추가해 준다.
8. 순회를 마친 후 정수형 변수 len에 lis의 크기 - 1만큼의 값을 저장해 준다.
9. 정수형 벡터 result를 초기화 하고, n - 1부터 0까지 역순하는 for문을 개행해 준다.
10. 만약 index의 i번째 요소가 len과 같다면 len을 감소시켜 준다.
11. 아니라면 result에 현재 A전깃줄이 위치한 값을 추가해 준다.
12. result의 크기를 출력하고, sort를 통해 result를 오름차순으로 정렬해 준다.
13. result에 저장된 값을 줄 바꿈을 기준으로 출력해 준다.

 

트러블 슈팅

1. lis에 push가 아닌 요소가 변경될 때 값을 result에 저장하여 출력하였다가 Fail을 받았다.
2. 경로 역추적 로직을 추가한 뒤 제출하니 AC를 받았다.

 

참고 사항

• 경로 역추적을 진행할 때 일치하는 경우 len의 인덱스만 감소시켜 준다.
• 일치 하지 않을 경우 result에 추가해 주어야 제거된 전깃줄의 A위치를 알 수 있다.
• n - 1부터 0까지 추적하였으므로, 출력하기 전 revsere나 sort를 통해 오름차순으로 정렬해 주어야 한다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
#define pii pair<int, int>
using namespace std;

int n;
vector<pii> lst;
vector<int> lis;

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int a, b; cin >> a >> b;
		lst.push_back({ a, b });
	}
	sort(lst.begin(), lst.end());

	vector<int> index(n);
	for (int i = 0; i < n; ++i) {
		pii cur = lst[i];
		auto it = lower_bound(lis.begin(), lis.end(), cur.second);
		index[i] = it - lis.begin();

		if (it == lis.end()) lis.push_back(cur.second);
		else *it = cur.second;
	}

	int len = lis.size() - 1;
	vector<int> result;
	for (int i = n - 1; i >= 0; --i) {
		if (index[i] == len) len--;
		else result.push_back(lst[i].first);
	}

	cout << result.size() << "\n";
	sort(result.begin(), result.end());
	for (int i : result) cout << i << "\n";
}