[G2] 백준 3066번 브리징 시그널 C++ 이분 탐색, lower_bound

리뷰

 

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

가장 긴 증가하는 부분 수열의 크기를 구하는 문제

 

 

전역 변수

• t : 테스트 케이스의 개수를 저장할 변수
• arr : 가장 긴 증가하는 부분 수열을 저장할 벡터

 

함수

없음

 

 

문제풀이

1. t값을 입력 받고, arr을 최대 N의 크기인 40000으로 reserve처리한다.
2. t번의 테스트 케이스를 수행하고, 변수 n을 초기화 후 포트의 개수 n을 입력 받는다.
3. 이전에 사용한 arr을 clear처리하고, n개의 포트 번호를 변수 x에 입력 받는다.
4. 변수 it에 lower_bound함수를 통해 arr에서 x이상인 이터레이터를 저장한다.
5. 만약 it이 arr의 end라면 arr에 x를 push하고, 아니라면 *it을 x로 변경한다.
6. 모든 작업을 마친 후 arr의 size를 출력 후 개행문자를 삽입한다.

 

트러블 슈팅

없음

 

 

참고 사항

• lower_bound를 사용해 가장 긴 증가하는 부분 수열의 크기를 구하는 전형적인 웰노운 문제다.

 

정답 코드

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

int t;
vector<int> arr;

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

	cin >> t;
	arr.reserve(40000);
	while (t--) {
		int n; cin >> n;
		arr.clear();

		for (int i = 0; i < n; ++i) {
			int x; cin >> x;
			auto it = lower_bound(arr.begin(), arr.end(), x);

			if (it == arr.end()) arr.push_back(x);
			else *it = x;
		}
		cout << arr.size() << "\n";
	}
	
}