1047번 : 울타리

boj.kr/1047

1047번: 울타리

아이디어 : 

기준을 나무가 아닌, 울타리, 즉 직사각형에 초점을 맞추자.

직사각형은 가로선 2개와 세로선 2개로 만들 수 있고, 가로선 2개의 안쪽 영역과 세로선 2개의 안쪽 영역의 겹치는 부분이 곧 직사각형의 내부 영역이 된다.

가로 기준으로 나무(=점) 2개, 세로 기준으로 점 2개를 골라서 이 4개의 점이 이루는 직사각형을 먼저 구한다.
그 다음 직사각형에 포함되는 점들과 포함되지 않는 점들로 나눈다.
포함되지 않는 점들은 다 잘라놓고, 포함되는 점들은 따로 모아둔다.
따로 모아둔, 직사각형에 포함되는 점들을 잘랐을 때 나무가 가장 많이 나오는 순서대로 정렬해두고, 그리디로 나무를 자른다.

구현 :

우선, 탐색이 용이하도록 좌표를 x기준으로 정렬한 배열과, y 기준으로 정렬한 배열을 준비한다.
x기준으로 점 2개, y기준으로 점 2개를 찾아야 하니 for문 4개를 중첩해두고,
찾은 점 4개를 이용해서 직사각형을 만든다.
모든 점들에 대해 이 직사각형에 포함되는지 안되는지 구분한다.(for문 하나 더)
포함되지 않는 나무들은 다 잘라놓고, 포함되는 나무들은 다시 정렬해서 나무가 많이 나오는 것들부터 잘라준다.

#include <bits/stdc++.h>
using namespace std;
struct node{
	int x,y,w,idx;
	node(int x, int y, int w, int idx):x(x),y(y),w(w),idx(idx){}
};
vector<node> ori;
vector<node> vx;
vector<node> vy;
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int N; cin>>N;
	for(int i=0; i<N; ++i){
		int u,v,w; cin>>u>>v>>w;
		ori.push_back(node(u,v,w,i));
		vx.push_back(node(u,v,w,i));
		vy.push_back(node(u,v,w,i));
	}
	sort(vx.begin(), vx.end(), [](node a, node b){
		if(a.x==b.x) return a.y<b.y;
		return a.x<b.x;
	});
	sort(vy.begin(), vy.end(), [](node a, node b){
		if(a.y==b.y) return a.x<b.x;
		return a.y<b.y;
	});
	int chk[41];
	vector<int> ww;
	int res=2e9;
	for(int xi=0; xi<N; ++xi){
		for(int xj=xi; xj<N; ++xj){
			for(int yi=0; yi<N; ++yi){
				for(int yj=yi; yj<N; ++yj){
					
					memset(chk,0,sizeof(chk));
					ww.clear();
					// xi, xj, yi, yj를 이용해서 직사각형을 만들 것.
					int minx=min(min(vx[xi].x, vx[xj].x), min(vy[yi].x, vy[yj].x));
					int maxx=max(max(vx[xi].x, vx[xj].x), max(vy[yi].x, vy[yj].x));
					int miny=min(min(vx[xi].y, vx[xj].y), min(vy[yi].y, vy[yj].y));
					int maxy=max(max(vx[xi].y, vx[xj].y), max(vy[yi].y, vy[yj].y));
					// 이 직사각형에 포함되지 않으면 바깥, 포함되면 안쪽으로 나눔(ww에 넣음).
					int k=(maxx-minx)*2+(maxy-miny)*2;
					int t=0;
					int cnt=0;
					for(int i=0; i<N; ++i){
						int curx=ori[i].x;
						int cury=ori[i].y;
						int curw=ori[i].w;
						if(curx>=minx && curx<=maxx && cury>=miny && cury<=maxy){
							ww.push_back(curw);
						}
						else{
							t+=curw;
							cnt++;
						}
					}
					sort(ww.begin(), ww.end());
					while(k>t && !ww.empty()){
						t+=ww.back();
						cnt++;
						ww.pop_back();
					}
					if(k<=t){
						res=min(res,cnt);
					}
				}
			}
		}
	}
	cout << res << '\n';
}