507 words
3 minutes
[BOJ] 수열 재배열
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
2s | 512MB | (3 ≤ N ≤ 2000, 2 ≤ K ≤ N) | BruteForce |
내가 연속된 구간 k개를 고르고 앞만 이어진다. 뒤만 이어진다. 앞뒤만 이어진다. 아니면 나만 보겠다… 이것만 고려해서 나눠서 풀면 되겠스비다.
이것도 학교에서 풀어서 영상은 없네용
정답 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include<set>
using namespace std;
int inf = 1e9;
int solution(int n, int k, vector<int>& nums){
// 그냥 나뒀을 때.. 는 이미 정렬할 대 되는거니까ㅏ상관 x
// 내가 장렬됨에 따라서 뒤와 앞이 이어지는경우
// 내가 정렬됨에 따라서 앞에를 버리고 뒤랑만 이어지는 경우
// 내가 정렬됨에 따라서 뒤를 버리고 앞만 이어지는경우
// 중복된거를 (length - 중복 개수)
vector<int> origin(n), reverse(n);
int result = 1;
origin[0] = 1;
reverse[n-1] = 1;
for(int i = 1; i < n; i++){
if(nums[i] <= nums[i-1]){
origin[i] = 1;
}else{
origin[i] = origin[i-1]+1;
result = max(origin[i], result);
}
}
for(int i = n-2; i > -1; i--){
if(nums[i+1] <= nums[i]) reverse[i] = 1;
else reverse[i] = reverse[i+1]+1;
}
set<int> current_set;
int start, end;
for(int i = 0; i <= n-k; i++){
current_set.clear();
for(int j = 0; j < k; j++) current_set.insert(nums[j+i]);
vector<int> current(current_set.begin(), current_set.end()); // 보통 정렬돼서 나오는 것처럼 보임..
sort(current.begin(), current.end()); // 그래도 불안해
// 앞뒤 이어지는 경우
if(current.size() == k && i > 0 && i < n-k){
start = 0;
end = current.size()-1;
if(current[start] > nums[i-1] && current[end] < nums[i+k]) result = max(result, end - start + 1 + origin[i-1] + reverse[i+k]);
}
// 앞만 이어지는 경우 | 앞 <- current -> 뒤
if(i > 0){
start = 0;
while(start < current.size()-1 && current[start] <= nums[i-1]) start++;
if(current[start] > nums[i-1]) result = max(result, origin[i-1] + (int) current.size() - start);
}
// 뒤만 이어지는 경우
if(i < n-k){
end = current.size()-1;
while(0 < end && current[end] >= nums[i+k]) end--;
if(current[end] < nums[i+k]) result = max(result, reverse[i+k] + end + 1);
}
result = max(result, (int)current_set.size());
}
return result;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int answer;
int n, k;
cin >> n >> k;
vector<int> nums(n);
for(int i = 0; i < n; i++) cin >> nums[i];
int result = solution(n, k, nums);
cout << result;
/*
10 3
1 8 2 4 8 5 1 8 9 3
5 4
*/
return 0;
}
[BOJ] 수열 재배열
https://compy07.github.io/Blog/posts/boj/27739/