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

리뷰

 

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

알고리즘 분류는 DP로 되어 있지만 기본적인 LIS(가장 큰 증가하는 수열) 문제이다.

 

 

전역 변수

• n : 주어지는 전깃줄의 개수를 저장할 변수
• ans : 정답을 저장할 변수

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, pair<int, int>(이후 pii) 타입의 오름차순 우선순위 큐 pq를 초기화 한다.
2. n개의 전깃줄 정보를 입력 받고, 전깃줄 A의 위치와 B의 위치를 묶어 pq에 push한다.
3. 정수형 벡터 lis를 초기화 한다.
4. pq가 빌 때 까지 while루프를 실행하고, 매 루프마다 요소를 한개씩 꺼내준다.
5. lower_bound 메서드를 통해 lis에 현재 요소의 B전깃줄의 위치 이상의 값이 있는지 찾아준다.
6. 만약 존재하지 않는다면, lis에 B전깃줄의 위치를 push해준다.
7. 존재한다면 해당 값을 B전깃줄의 위치로 변경하고 ans를 증가시켜 준다.
8. 모든 탐색이 종료된 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.
• A전봇대와 연결되는 위치의 번호를 기준으로 내림차순 정렬한다.

 

정답 코드

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

int n, ans;

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

	cin >> n;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	while (n--) {
		int a, b; cin >> a >> b;
		pq.push({ a, b });
	}

	vector<int> lis;
	while (!pq.empty()) {
		pii cur = pq.top(); pq.pop();
		auto it = lower_bound(lis.begin(), lis.end(), cur.second);
		if (it == lis.end()) lis.push_back(cur.second);
		else {
			*it = cur.second;
			ans++;
		}
	}
	cout << ans;
}