[G2] 백준 2352번 반도체 설계 C++ LIS, 가장 긴 증가하는 부분 수열

리뷰

 

LIS는 꼭 풀어봤으면 좋겠다. 난이도에 비해 코드길이가 정말 짧다! 꿀통 알고리즘

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

 

문제 풀이

1. 포트의 개수 n개를 입력 받고 LIS를 저장할 정수형 벡터 ans를 초기화 해준다.
2. n개의 입력을 받고, 입력 받은 포트 번호가 기존의 포트보다 크다면 ans에 push 해준다.
3. 만약 기존의 포트보다 작거나 같으면 해당 포트의 위치를 찾아 교체해 주면 된다.
4. 반복이 종료된 후 ans의 size를 출력해 주면 된다.

 

참고 사항

lower_bound를 사용하려면 algorithm을 include 해주어야 한다.

 

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

	int n; cin >> n;
	vector<int> ans;
	while (n--) {
		int port; cin >> port;
		auto it = lower_bound(ans.begin(), ans.end(), port);
		if (it == ans.end()) ans.push_back(port);
		else *it = port;
	}
	cout << ans.size();
}