반응형
https://www.acmicpc.net/problem/2352
문제 해결 알고리즘
LIS알고리즘 (최장 증가 부분 수열 알고리즘)을 써준다.
이 때, $O(n \mathrm{log} n)$ 알고리즘을 사용한다 (이분 탐색).
https://kimmessi.tistory.com/191?category=871925
자세한 내용은 위의 링크를 참고
소스 코드
#include <bits/stdc++.h>
#define MAX 1000001
using namespace std;
int arr[MAX];
int LIS[MAX];
int binary_search(int left, int right, int target){
int mid;
while(left < right){
mid = (left + right) / 2;
if(LIS[mid] < target) left = mid + 1;
else right = mid;
}
return right;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N; cin >> N;
for(int i=0;i<N;i++){
cin >> arr[i];
}
int j = 0, i = 1;
LIS[0] = arr[0];
while(i < N){
if(LIS[j] < arr[i]){
LIS[j+1] = arr[i];
j++;
}
else {
int idx = binary_search(0, j, arr[i]);
LIS[idx] = arr[i];
}
i++;
}
cout << j+1 << '\n';
}
반응형
'알고리즘 문제 해결 > BOJ' 카테고리의 다른 글
[LIS, DP] BOJ 11053 가장 긴 증가하는 부분 수열 (C++) (0) | 2022.06.13 |
---|---|
[LIS, 이분 탐색] BOJ 14003 가장 긴 증가하는 부분 수열 5 (C++) (0) | 2022.06.07 |
[MST, UnionFind] BOJ 1647 도시 분할 계획 (0) | 2022.05.24 |
[다익스트라] BOJ 1916 최소비용 구하기 (C++) (0) | 2022.05.20 |
[MST] BOJ 4386 별자리 만들기 (0) | 2022.05.17 |