[G2] 백준 1365번 꼬인 전깃줄 C++ 이분 탐색, LIS

리뷰

 

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

lower_bound를 사용하여 가장 긴 증가하는 부분 수열을 구하는 문제

 

 

전역 변수

• n : 전봇대의 개수를 저장할 변수
• ans : 정답을 저장할 변수

 

함수

없음

 

 

문제풀이

1. 정수형 벡터 lis를 초기화 해준다.
2. n값을 받아 주고, n번의 while루프를 수행해 준다.
3. 매 루프마다 정수형 변수 num에 오른편 전봇대의 위치를 받아준다.
4. lower_bound 함수를 통해 lis에서 num이상인 값의 이터레이터를 it에 저장해 준다.
5. it이 lis의 end라면 lis에 num을 push해준다.
6. 아니라면 ans를 증가시키고, it의 위치의 값을 num값으로 변경해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

없음

 

 

정답 코드

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

int n, ans;

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

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