[S2] 백준 11053번 가장 긴 증가하는 부분 수열 C++ 이분 탐색, lower_bound

리뷰

 

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

DP는 대체 어떻게 해야 늘까... 그냥 웰노운 풀이인 이분 탐색으로 풀어버렸다.

 

 

전역 변수

• n : 수열의 크기를 저장할 변수
• lst : 가장 긴 증가하는 수열을 만들기 위한 벡터

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n번의 for문을 개행 후 매 루프마다 변수 a에 값을 입력받는다.
2. 변수 it에 lower_bonud함수를 통해 lst벡터에 a이상인 이터레이터를 저장한다.
3. it이 lst.end()라면 lst에 a를 추가하고, 아니라면 it의 값을 a로 변경한다.

 

트러블 슈팅

없음

 

 

참고 사항

없음

 

 

정답 코드

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

int n;
vector<int> lst;

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int a; cin >> a;
		auto it = lower_bound(lst.begin(), lst.end(), a);
		if (it == lst.end()) lst.push_back(a);
		else *it = a;
	}
	cout << lst.size();
}