[백준 알고리즘] 1047번 울타리 c++

처음엔 조합으로 접근하였으나 시간초과로 실패했다. 

n개의 나무 중에서 1, 2, .... n-1를 제거했을 때 울타리를 만들 수 있나 확인하도록 구현하였으나

n의 최대값은 40으로 당연히 시간초과가 나온다.

 

결과적으로 구현한 방법은 N^5 로 5중 for문을 통해 구현하였다.

직사각형을 만들 때, 그 직사각형의 꼭지점은

직사각형 내부 나무들 중 x와 y의 최소, 최대값을 4개의 꼭지점으로 해야 

펜스 설치 시에 낭비되는 나무가 없을 것이다. 

 

n개의 나무가 주어졌을 때 만들 수 있는 직사각형의 모든 경우를 구하면

x값을 오름차순 정렬한 xsort와 y값을 오름차순한 ysort값을 4중 for문을 통해 구할 수 있다.

  

각 직사각형에서 해당 직사각형이 펜스를 만들 수 있는 지 확인하고 이 중 벤 나무가 최소인 경우를 구해야 한다.

 

1. 직사각형 외부의 nfence값을 더한 값(out_sum)이 need(직사각형 크기)보다 큰 지

2. 1.은 만족하지 못하지만 직사각형 내부의 나무를 추가로 베면 need보다 큰 지

- 벤 나무를 최소화 해야하므로 가장 큰 nfence값을 가진 나무부터 순차적으로 확인한다.(in 벡터)

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	int n;
	cin >> n;

	int res = n;

	vector<int> x(n), y(n), nfence(n), xsort(x), ysort(x);

	for(int i=0; i<n; i++){
		cin >> x[i] >> y[i] >> nfence[i];
		xsort[i] = x[i];
		ysort[i] = y[i];
	}

	sort(xsort.begin(), xsort.end());
	sort(ysort.begin(), ysort.end());

	vector<int> in;

	for(int a=0; a<n; a++){ for(int b=a; b<n; b++){
		for(int c=0; c<n; c++){ for(int d=c; d<n; d++){
			int ntree = 0, out_sum =0, in_sum =0;
			int need = 2*(xsort[b] - xsort[a] + ysort[d] - ysort[c]);

			for(int i=0; i<n; i++){
				if(x[i] >= xsort[a] && x[i] <= xsort[b]
						&& y[i] >= ysort[c] && y[i] <= ysort[d]){
					 ntree ++;
					 in.push_back(nfence[i]);
					 in_sum += nfence[i];
				}
				else{
					out_sum += nfence[i];
				}	
			}//i

			if(out_sum >= need){
				res = min(res, n- ntree);
			}
			else{
				if(out_sum + in_sum >= need){
					sort(in.begin(), in.end(), greater<int>());
					for(int i=0; i<in.size(); i++){
						ntree--;
						out_sum += in[i];
						if(out_sum >= need){
							res = min(res, n- ntree);
							break;
						}
					}
				}
			}
			in.clear();
		}}
	}}

	cout << res << endl;

	return 0;
}