늘
acmicpc_12738(가장 긴 증가하는 부분 수열 3)(LIS) 본문
728x90
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[1000001];
vector<int> v;
int x;
int main() {
int n;
cin >> n;
v.push_back(-1000000001);
for (int i = 0; i < n; ++i) {
cin >> x;
if (v.back() < x) {
v.push_back(x);
}
else {
auto it = lower_bound(v.begin(), v.end(), x);
*it = x;
}
}
cout << v.size() - 1;
}
기존의 LIS코드를 이용했는데 O(n^2)이 나오면서 시간초과가 나왔다.. 너무 뻔하다고 생각했는데 예상대로였다. 그래서 LIS에 대해서 더 알아보니 이분탐색 방법과 세그먼트 트리를 이용하는 방법이 있다고 한다. 그 중에서 이분탐색 방법을 이용해서 해결해 보았다.
기존의 O(n^2)알고리즘보다 더욱 간단해서 조금 놀랐다!
참고로, lower_bound(v.begin(), v.end(), x)는 vector v를 돌면서 x이상은 수의 위치를 찾는 함수이다!
728x90
'알고리즘_백준 > DP' 카테고리의 다른 글
[백준] C/C++ 퇴사 [삼성 SW 역량 테스트 기출 문제 ] (0) | 2021.10.05 |
---|---|
acmicpc_14585(사수빈탕) (0) | 2021.02.21 |
acmicpc_2293(동전 1) (0) | 2021.02.19 |
acmicpc_1005(ACM Craft) (0) | 2021.02.16 |
Comments