반응형
https://www.acmicpc.net/problem/2568
문제 해결 알고리즘
LIS알고리즘에서 길이와 수열을 구하는 문제이다.
좀 달랐다면 여기서는 제거해야할 원소의 갯수와 위치를 출력한다는 점인데,
그 부분은 record 배열에서 LIS가 아닌 부분을 출력하면 그만인 문제이다.
아래의 링크에 자세한 설명이 있다.
https://kimmessi.tistory.com/191
소스 코드
#include <bits/stdc++.h>
using namespace std;
int N;
int arr[500010], LIS[500010], record[500010];
int MAX = 0, MAX_num = 0, start_num = 500010;
stack<int> result;
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);
cin >> N;
for(int i=0;i<N;i++){
int idx, num;
cin >> idx >> num;
MAX_num = max(MAX_num, idx);
start_num = min(start_num, idx);
arr[idx] = num;
}
int j = 1, i = start_num+1;
LIS[1] = arr[start_num];
record[start_num] = 1;
while(i <= MAX_num){
if(LIS[j] < arr[i]){
LIS[++j] = arr[i];
record[i] = j;
}
else{
if(arr[i] == 0) record[i] = 0;
else{
int idx = binary_search(1, j, arr[i]);
LIS[idx] = arr[i];
record[i] = idx;
}
}
MAX = max(MAX, record[i]);
i++;
}
for(int i=MAX_num;i>0;i--){
if(record[i] == 0) continue;
if(MAX == record[i]) MAX--;
else result.push(i);
}
cout << result.size() << '\n';
while(!result.empty()) {
cout << result.top() << '\n';
result.pop();
}
}
반응형
'알고리즘 문제 해결 > BOJ' 카테고리의 다른 글
[위상 정렬] BOJ 1766 문제집 (C++) (0) | 2022.06.22 |
---|---|
[위상 정렬] BOJ 2252 줄 세우기 (0) | 2022.06.22 |
[위상 정렬] BOJ 1005 ACM Craft (0) | 2022.06.20 |
[위상 정렬] BOJ 2056 작업 (0) | 2022.06.19 |
[위상 정렬] BOJ 14567 선수과목 (Prerequisite) (0) | 2022.06.18 |