반응형
https://www.acmicpc.net/problem/12738
문제 해결 알고리즘
이분 탐색을 이용한 LIS알고리즘을 이용한다.
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;
}
반응형
'알고리즘 문제 해결 > BOJ' 카테고리의 다른 글
[위상 정렬] BOJ 14567 선수과목 (Prerequisite) (0) | 2022.06.18 |
---|---|
[백트래킹] BOJ 9663 N-Queen (0) | 2022.06.14 |
[LIS, DP] BOJ 11053 가장 긴 증가하는 부분 수열 (C++) (0) | 2022.06.13 |
[LIS, 이분 탐색] BOJ 14003 가장 긴 증가하는 부분 수열 5 (C++) (0) | 2022.06.07 |
[LIS, 이분 탐색] BOJ 2352 반도체 설계 (C++) (0) | 2022.06.07 |