백준 1047: 울타리

https://www.acmicpc.net/problem/1047

 

이 문제의 해결책은 생각보다 간단하지만, 떠올리기엔 고전하였다.

 

그리디적으로 생각하면, 가장 많은 울타리를 만들수 있는 나무를 베는 것이 상책이다.

하지만, 이것도 해당 나무의 위치에 따라 다르다. 따라서 다른 방법이 필요하다.

 

N은 최대 40이다. 그렇다면 Bruteforce를 사용할 수 있지 않을까?

직사각형은 두 개의 점만 있다면 구성할 수 있다.

나무를 꼭짓점으로 둔 직사각형을 Bruteforce해서 찾아서 해당 직사각형 없는 나무를 활용해서 해당 직사각형 둘레를 만들 수 있는지 확인해서 자르는 나무의 최솟값을 구하면 되면 해결할 수 있을 것 같다.

 

직사각형 내의 나무를 자르는 경우의 수도 있다. 이런 경우엔 직사각형 안의 가장 많은 울타리 수를 차례대로 자르고, 울타리를 구성할 수 있을 때, 답과 비교하면 된다.

 

조금 더 생각을 해보자, 기존의 방식은 나무가 꼭짓점에 있다는 것을 전제로 이야기했는데, 만약 꼭짓점에 없다면? 

예로

3

3 1 1000

1 5 1000

7 7 1000

이 경우엔 꼭짓점이 (1, 1), (7, 7)로, 위의 Bruteforce 방식으로 답을 구할 수 없다.

그렇다면, 시간복잡도를 더욱 늘리자, N = 40이라서 아직 더 나아갈 수 있다.

 

x 좌표와 y 좌표를 따로 저장해서, 각각에 두 점씩 고른뒤에, 해당 직사각형을 만들기 위해서 베야하는 나무의 갯수를 구하면 된다.

위의 예시를 다시 예로 들면, x = {1, 3, 7}, y = {1, 5, 7} 이런 식으로 배열을 나누고,

{(1, 3), (1, 5)}, {(1, 3), (1, 7)}, {(1, 3), (5, 7)}, {(1, 7), (1, 5)} ....

이런식으로 각 직사각형 꼭짓점으로 두고 계산한다.

이 문제는 마침 모든 나무의 x좌표는 같지 않고, y좌표는 같지 않다고 기술되었기 때문에, 중복 체크를 할 번거로움이 줄어들었다.

 

이 해결책은

https://sumserv.tistory.com/109

백준 7573: 고기잡이

위의 문제처럼 예전에 해결했던 문제에서 아이디어를 따왔다.

이러면 대략 O(N ^ 5)로 내가 해결한 Bruteforce 문제 해결책 중에서도 손꼽히는 시간복잡도지만

N=40이라서 시험해볼 가치가 있다.

 

구현을 쉽게 하기 위해 x좌표와 y좌표를 정렬하면 더욱 좋다.

for(int xidx1 = 0; xidx1 < N; xidx1++)
	for(int xidx2 = xidx1 + 1; xidx2 < N; xidx2++)
		for(int yidx1 = 0; yidx1 < N; yidx1++)
			for (int yidx2 = yidx1 + 1; yidx2 < N; yidx2++)
				for(int idx = 0; idx < N; idx++)
                		{
                        		// ... 계산식
                		}

한편 이런식으로 한 뒤에 답을 제출했었는데, 41% 쯔음에 틀렸었다.

다시 한번 문제를 살펴보자.

 

"가로 세로의 길이 중 하나가 0이어도 직사각형이며, 모두 0이어도 직사각형이다"

 

라 적혀있다. 즉, 직사각형의 꼭짓점의 x좌표, y좌표는 같을 수 있다.  그렇다면

(int xidx2 = xidx1 + 1, int yidx2 = yidx1 + 1)) 이 아니라 (int xidx2 = xidx1, int yidx2 = yidx1)이 되어야한다.

그렇게 나온 최종코드는 다음과 같다.

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

using namespace std;

vector<int> x, y, arr;
int N, X[41], Y[41], C[41], ans = 1e9 + 7;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> X[i] >> Y[i] >> C[i];
		x.push_back(X[i]); y.push_back(Y[i]);
	}
	sort(x.begin(), x.end()); sort(y.begin(), y.end());
	for(int xidx1 = 0; xidx1 < N; xidx1++)
		for(int xidx2 = xidx1; xidx2 < N; xidx2++)
			for(int yidx1 = 0; yidx1 < N; yidx1++)
				for (int yidx2 = yidx1; yidx2 < N; yidx2++)
				{
					int cnt = 0, s = 0, r = 2 * (x[xidx2] - x[xidx1]) + 2 * (y[yidx2] - y[yidx1]);
					for(int idx = 0; idx < N; idx++)
						if (x[xidx1] <= X[idx] && X[idx] <= x[xidx2] && y[yidx1] <= Y[idx] && Y[idx] <= y[yidx2])
						{
							arr.push_back(C[idx]);
						}
						else
						{
							++cnt;
							s += C[idx];
						}
					sort(arr.begin(), arr.end());
					for (int i = arr.size() - 1; i >= 0 && s < r; i--, cnt++)
					{
						s += arr[i];
					}
					if (s >= r)
					{
						ans = min(ans, cnt);
					}
					arr.clear();
				}
	cout << ans << '\n';
}

 

처음 봤을 때 다소 막막했던 문제였지만, 이렇게 자력으로 해결하니 꽤나 큰 성취감을 느낀다.