


백준 12015 가장 긴 증가하는 부분 순열 2
백준 12015 가장 긴 증가하는 부분 순열 2
2022년 11월 28일
2022년 11월 28일
cpp, 이분 탐색
문제
문제
풀이
풀이
해당 문제를 일반적인 동적 계획법으로 풀면 시간복잡도 o(n*n)으로 시간초과가 난다.
하지만 이진 탐색을 이용해서 풀면 o(logn)에 해결 가능하다.
코드
코드
#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
vector<int> arr;
cin >> n;
for(int i=1; i<=n; ++i){
int val; cin >> val;
if(arr.empty() || arr.back() < val) arr.push_back(val);
else{
auto target = lower_bound(arr.begin(),arr.end(),val);
*target = val;
}
}
cout << arr.size();
}
결과
결과

Copyright © 2024 Hyunghoon Kim