[백준 12015] 가장 긴 증가하는 부분 수열 2

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

---

해설

이번 문제는 LIS 문제인데, 내가 아는 LIS 소스코드와 다르게 풀어야 해서 한번 가져와봤다.

좀 고급 LIS 느낌이다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001];
int num[1001];
int main() {
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	int res = -1;
	for (int i = 0; i < n; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++)
			if (num[j] < num[i])
				dp[i] = max(dp[i], dp[j] + 1);
		res = max(res, dp[i]);
	}
	cout << res << '\n';
}

위에 코드는 원래 내가 쓰던 LIS 코드인데, 저기서 배열 크기만 바꿔서 제출했더니 시간초과가 떴다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> vt;
auto it = vt.begin();
int main() {
	int n, data;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> data;
		if (i == 0) vt.push_back(data);
		if (vt.back() < data) vt.push_back(data);
		else {
			it = vt.begin();
			it = lower_bound(vt.begin(), vt.end(), data);
			*it = data;
		}
	}
	cout << vt.size() << '\n';
}

 

코드는 다음과 같다.

lower_bound가 보이듯이 이진탐색을 사용 해 LIS를 만들었다.

 

for문으로 수열을 입력 받는다.

첫번째로 입력받은 수열은 vt라는 벡터 배열에 넣어준다.

만약 vt 벡터의 맨 끝이 현재 받은 data 보다 작으면 data를 vt 벡터 끝에 넣어준다.

그것도 아니라면 이터레이터 it 를 선언 후 data가 어디 쯤 들어갈 수있는지 위치를 찾는다.

위치를 찾은 후 그 위치에 data를 넣어준다.

 

어떻게 이런 생각을 했는 지는 모르겠는 데, 잘 돌아간다.

더 공부해봐야겠다.