나는 병신임을 이 문제로 다시 깨달았다
스위핑 라인 관련 문제를 1개정도밖에 예~~~~전에 풀어봤어서 쉽사리 갈피를 잡지 못하였기에
이 "갈피"를 블로그를 통해 잡았다....병신새기 진짜 티어값 못하는듯
어쨌든 그 "갈피" 란 다음과 같다: 철로 문제에서, 구하고자 하는 것은, 오른쪽 점에서 왼쪽으로 길이 d
만큼의 구간 내에(혹은 경계에) 있는 라인 수라는 것
이 "갈피"를 잡고 나서 이제 곧 최적화를 해야 됨을 알게 되었고, 이는 꽤 쉬웠다
본인은 "보석 도둑"이라는 골드2 그리디 문제에서 상당히 많은 영감을 얻었었다. 그 중에서
하나가 반복문에서 돌려도 크기가 단조감소하기에 그냥 O(N)이라는 거였는데, 이에 착안했다.
우선순위 큐를 왼쪽 기준 오름차순, 오른쪽 기준 오름차순 순의 우선순위로 정렬(보통 나는 이 방법을
pq에 -넣어서 구현한다) 하도록 한다.
이후 오른쪽 점의 오름차순, 왼쪽 점의 내림차순으로 정렬한 라인들을 따라 차례로 진행하면서
각각을 우선 pq에 넣고(물론 -곱해서) 자기의 d-구간(오른쪽 기준 왼쪽으로 길이가 d인 구간)에 포함되지 않는
점들을 pq에서 차례로 pop해준다. 이후 남은 것 가지고 개수세기.
이는 현재에 완전히 포함되지 않는 점은 다음 순서에서 반드시 포함될 수 없기 때문으로, 이는 구간이 점점
오른쪽으로 이동함을 통해 자명히 알 수 있다.
하....이런 아이디어로 pq 최적화가 가능하다. 이는 최적화 자체는 쉬운데 처음 갈피를 잡기 어려운 케이스였다,
생각을 좀 깊게 해야겠다.
아래는 소스 코드이다.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n, L, sum, maxx;
vector<pair<ll, ll>> v;
priority_queue<pair<ll, ll>> pq;
bool comp(pair<ll, ll> x1, pair<ll, ll> x2){
if(x1.second==x2.second){
return x1.first>x2.first; // left 기준 내림차순
}
return x1.second<x2.second; // right기준 오름차순
}
pair<ll, ll> operator-(pair<ll, ll> p){
return {-p.first, -p.second};
}// 연산자 오버로딩: pair형
int main(){
cin >> n;
v.resize(n);
for(ll i=0;i<n;i++){
cin >> v[i].first >> v[i].second;
if(v[i].first>v[i].second) swap(v[i].first, v[i].second);
}
sort(v.begin(), v.end(), comp);// right 기준 오름차순 정렬
cin >> L;
// (v[i].first-L, v[i].first)구간에서 자신과 겹치는 라인 수 찾기: first 기준 오름차순 정렬
for(ll i=0;i<n;i++){
pq.push({-v[i].first, -v[i].second});
ll l=v[i].second-L, r=v[i].second;
while(!pq.empty()){
pair<ll, ll> now=-pq.top();
if(now.first>=l and now.second<=r) break;
else pq.pop();
}
sum=pq.size();
if(maxx<sum) maxx=sum;
}
cout << maxx;
}연산자 오버로딩은 굳?이지만 요즘 C++ 문법을 배우고 있어서 한 번 해 봤다 ㅎ
머리가 좋아지고 싶다.....하고 싶은 건 너무 많은데 능지이슈로 벽에 부딪힌다 느끼는 경우가 꽤 있기 때문이다.
그럴 때마다 끝없는 자괴감에 빠진다.
이건 내가 그런 인간인 것도 한 몫 하는 듯싶다.
무튼.
여러분도 힘내시라. 언젠가는 힘든 시간도 끝난다. 올 지 않을 것 같았던 종강도 오고, 졸업도 올 것이다.