반응형
https://www.acmicpc.net/problem/14003
문제 해결 알고리즘
똑같이 이분탐색을 쓴 LIS 알고리즘을 이용해주는데 이 때,
진짜 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 record[MAX];
int result_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];
record[0] = 1;
while(i < N){
if(LIS[j] < arr[i]){
LIS[j+1] = arr[i];
j++;
record[i] = j+1;
}
else {
int idx = binary_search(0, j, arr[i]);
LIS[idx] = arr[i];
record[i] = idx+1;
}
i++;
}
cout << j+1 << '\n';
int cnt = 0;
int result_MAX = j+1;
for(int i=N-1;i>=0;i--) {
if(record[i] == result_MAX){
result_lis[cnt++] = arr[i];
result_MAX--;
}
}
for(int i=cnt-1;i>=0;i--){
cout << result_lis[i] << ' ';
}
}
반응형
'알고리즘 문제 해결 > BOJ' 카테고리의 다른 글
[LIS, 이분 탐색] BOJ 12738 가장 긴 증가하는 부분 수열 3 (C++) (0) | 2022.06.13 |
---|---|
[LIS, DP] BOJ 11053 가장 긴 증가하는 부분 수열 (C++) (0) | 2022.06.13 |
[LIS, 이분 탐색] BOJ 2352 반도체 설계 (C++) (0) | 2022.06.07 |
[MST, UnionFind] BOJ 1647 도시 분할 계획 (0) | 2022.05.24 |
[다익스트라] BOJ 1916 최소비용 구하기 (C++) (0) | 2022.05.20 |