산책길
문제 해석
나무의 좌표와 산책로가 주어졌을 때, 각 산책로를 건설하려면 나무를 몇개나 베어야 하는지 출력하는 문제입니다.
산책로는 축에 평행한 직사각형으로 나타냅니다.
설계(X)
정렬 + 이분탐색을 활용한 문제입니다.
아이디어를 생각치 못해서 Croatian Olympiad 대회에서 제공하는 솔루션을 참조하였습니다.
아이디어는 다음과 같습니다.
먼저, X축과 Y축 기준으로 정렬한 두가지의 좌표를 저장해놓습니다.
(x1,y1)~(x2,y2)로 이루어진 산책로는 4개의 선분으로 이루어져 있습니다.
그러므로, {(x1,y1),(x1,y2)},{(x2,y1),(x2,y2)},{(x1+1,y1,x2-1,y1)},{(x1+1,y2,x2-1,y2)}로 이루어진 선분을 각각 조사하면 됩니다.
여기서, x1+1과 x2-1을 한 이유는 나머지 두개의 선분에서 해당 좌표를 포함하기 때문에 겹치지 않는 방식으로 진행하기 위함입니다.
X에 대해서 정렬한 좌표를 이분탐색으로 탐색하여 가로 선분들에 포함되는 나무의 개수를 카운트합니다.
마찬가지로 Y에 대해서 정렬한 좌표를 탐색하여 세로 선분들에 포함되는 나무의 개수를 카운트합니다.
포함 범위를 찾기 위해서 upper_bound와 lower_bound함수를 이용합니다.
구현(X)
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> pp;
vector<pp> tree_x,tree_y;
int N,P;
bool comp_x(pp a, pp b){
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
}
bool comp_y(pp a, pp b){
if (a.second != b.second) return a.second < b.second;
return a.first < b.first;
}
int go(vector<pp>& tree ,bool comp(pp a, pp b), pp a, pp b){
return upper_bound(tree.begin(),tree.end(),b,comp)-lower_bound(tree.begin(),tree.end(),a,comp);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N ;
tree_x = vector<pp>(N,{0,0});
tree_y = vector<pp>(N,{0,0});
for (int i = 0 ;i <N; i++){
cin >> tree_x[i].first >> tree_x[i].second;
tree_y[i] = tree_x[i];
}
sort(tree_x.begin(),tree_x.end(),comp_x);
sort(tree_y.begin(),tree_y.end(),comp_y);
cin >> P;
for (int i = 0 ;i < P; i++){
int x1,x2,y1,y2;
cin >> x1 >> y1 >> x2 >> y2;
int ans = 0;
ans += go(tree_x,comp_x,pp(x1,y1),pp(x1,y2));
ans += go(tree_x,comp_x,pp(x2,y1),pp(x2,y2));
ans += go(tree_y,comp_y,pp(x1+1,y1),pp(x2-1,y1));
ans += go(tree_y,comp_y,pp(x1+1,y2),pp(x2-1,y2));
cout << ans <<"\n";
}
return 0;
}
디버깅
upper_bound와 lower_bound를 comp함수를 기반으로 직접 구현하려고 했으나, 제가 기존에 사용하던 이분탐색방법과 로직이 맞지 않는것 같았습니다.
엣지케이스에서 자꾸 다른 값을 내어서, 추후에 upper_bound를 다시 구현해봐야 할 것 같습니다.
제출결과
364 ms
마무리
정렬과 이분탐색기법을 이용하는 문제였습니다.
이분탐색을 연습하기에 아주 적절한 문제인 것 같습니다.