알고스팟 울타리 잘라내기

https://algospot.com/judge/problem/read/FENCE

algospot.com :: FENCE

 

 

<접근방법>

하나하나 비교하는 방법은 n의 크기를 고려했을 때, 당연히 안된다고 생각했다.

그래서 반띵을 해가며 풀어야겠다는 생각을 했다. 하지만 더 이상 쓸만한 생각이 떠오르지 않았다.

그리고 책을 보았다.

 

책에서 나온 해결방법은 이러하다.

1. 반띵한다.

2. 이때 가장 큰 직사각형은 반띵선을 기준으로 왼쪽 혹은 오른쪽에만 속할 수 있다.

이것은 각각에 대해 재귀호출을 하여 해결한다.

3. 남은 하나의 경우는 반띵선에 걸쳐서 가장 큰 직사각형이 있는 경우이다.

이것을 시간 안에 잘구현하면 문제끝~~

 

그럼 3번을 어떻게 할 것이냐?

우선 반띵선 양 옆에 있는 직사각형 두 개를 합친다. 왜냐? 반띵선이 무조건 포함된 경우를 생각하고 있기 때문이다.

 

그 다음 양 옆에 있는 직사각형 두 개 중에 더 큰 놈을 선택해서 확장시킨 후

가장 큰 직사각형의 넓이를 갱신한다.

 

 

---

 

 

<시간복잡도>

반띵하며 재귀호출 -> lgn

함수 하나의 연산시간->n

=>O(nlgn)

 

 

 

---

 

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;

int tc, n;
int h[20000];
int res;

int solve(int left, int right) {
	//판자의 개수가 하나일때
	if (left == right) {//이거 생각못함
		return h[left];
	}

	int mid = (left + right) / 2;

	//왼쪽에서만 떼어냄, 오른쪽에서만 떼어냄을 고려
	int res = max(solve(left, mid), solve(mid+1, right));

	int low = mid;
	int high = mid+1;
	int height = min(h[low], h[high]);

	//양쪽에 걸쳐진 경우를 생각하므로
	//양쪽에 걸친 최소의 케이스에서 시작한다.
	res = max(res, height*2);

	//양쪽으로 한 칸씩 확장한다.
	//이때 왼쪽, 오른쪽 중 더 큰 쪽으로 확장한다.
	while (left < low || high < right) {
		//오른쪽으로 확장이 가능하면서 (오른쪽이 더 크거나 왼쪽으로는 확장이 불가능할 때 )
		//오른쪽으로 확장한다.
		if (high < right && (low == left || h[high+1] > h[low-1])) {//이 부분 지리네
			high++;
			height = min(height, h[high]);
		}
		else {
			low--;
			height = min(height, h[low]);
		}
		res = max(res, height * (high - low + 1));
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> h[i];
		}
		cout << solve(0, n-1) << '\n';
	}

	return 0;
}

 

 

---

 

 

<느낀점>

반띵까지는 생각했어도 그 다음에는 어떻게 해야할지 전혀 몰랐다.

분할정복에 안익숙해서 그런거 같다.

문제 자체를 외워야겠다.

또 기저사례를 생각하지 못했다. 재귀를 할 때는 유의하도록 하자.