BOJ 12015. 가장 긴 증가하는 부분 수열 2
랭크 : 골드2
문제 풀이
최장 증가 부분 수열(LIS) 알고리즘으로 간단하게 해결 가능합니다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int main() {
fastio;
int N, tmp;
cin >> N;
vector<int> line;
for (int i=0; i < N; i++) {
cin >> tmp;
auto iter = lower_bound(line.begin(), line.end(), tmp);
if (iter == line.end()) line.push_back(tmp);
else *iter = tmp;
}
cout << line.size() << endl;
}알고리즘 |
시간복잡도 |
공간복잡도 |
|---|---|---|
| LIS | $O(N logN)$ | $O(N)$ |
'알고리즘 > 백준' 카테고리의 다른 글
| BOJ 2239. 스도쿠 (0) | 2022.07.11 |
|---|---|
| BOJ 9252. LCS 2 (0) | 2022.07.11 |
| BOJ 12852. 1로 만들기 2 (0) | 2022.07.10 |
| BOJ 2166. 다각형의 면적 (0) | 2022.07.10 |
| BOJ 2568. 전깃줄 - 2 (0) | 2022.07.10 |