알고스팟_울타리 잘라내기_ 분할정복

2020-04-24 · 배운 것 · 5분 읽기

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

algospot.com ::
FENCE

풀이방식들

이 문제의 풀이방법은
1. 세그먼트 트리 + 분할정복 방식 (밑의 url 참고)
https://blog.fxjodo.com/blog/11/

히스토그램에서 가장 큰 직사각형 _ 백준 6549번

2. 종만북에서 나온 분할정복 방식
3. 스택을 이용한 방식

3가지가 있다. 이번에는 이 중에서 2번째 방법으로 푸는 방법을 설명하겠다.

풀이방법

일반적인 분할정복 방식은 잘 알것이다.

하지만, 이 방식만으로는 이걸 풀수가 없는데, 그 이유는 답이 왼쪽부분과 오른쪽 부분에 걸쳐 있을수 있기 때문이다.

그래서 책에서 제시한 방법은

1. 원래의 분할정복처럼 left +right /2 하여 mid를 구한다.
2. 디폴트로 lo = mid, hi = mid+1 로 두고
3. 높이가 큰 순서대로 lo-- or hi++을 반복한다.
4. 이때 lo-- or hi++ 할때마다 넓이를 구해 최대넓이인지 비교한다.
5. 기저조건인 left == right가 나올때까지 재귀 1~4반복

코드로 보자면 이렇다.

while (left < lo || hi < right)
{
	if (hi < right && (lo <= left || h[lo - 1] < h[hi + 1]))
	{
		hi++;
		height = min(height, h[hi]);
	}
	else
	{
		lo--;
		height = min(height, h[lo]);
	}
	ret = max(ret, height * (hi - lo + 1));
}

시간복잡도

함수내에서는 재귀호출, 두 부분에 걸쳐있는 사각형을 찾는 작업 두가지 일을 한다.
재귀호출 -> O(logn),
두 부분에 걸쳐있는 사각형을 찾는 작업 -> 너비가 2부터 ~ n인 사각형을 하나하나 검사 -> O(n)

그러므로 시간복잡도는 O(nlogn) 이다.

전체코드

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

using namespace std;

vector<int> h;

int solve(int left, int right)
{
	//기저사례
	if (left == right)
		return h[left];

	int mid = (left + right) / 2;
	int ret = max(solve(left, mid), solve(mid + 1, right));
	int lo = mid, hi = mid + 1;
	int height = min(h[lo], h[hi]);
	ret = max(ret, height * 2);

	while (left < lo || hi < right)
	{
		if (hi < right && (lo <= left || h[lo - 1] < h[hi + 1]))
		{
			hi++;
			height = min(height, h[hi]);
		}
		else
		{
			lo--;
			height = min(height, h[lo]);
		}
		ret = max(ret, height * (hi - lo + 1));
	}
	return ret;
}

int main()
{
	int c;
	cin >> c;
	for (int i = 0; i < c; i++)
	{
		h.clear();
		int n;
		cin >> n;
		int value;
		for (int j = 0; j < n; j++)
		{
			cin >> value;
			h.push_back(value);
		}

		//solve rr
		cout << solve(0, h.size() - 1) << endl;
	}
	return 0;
}

후기

어떻게 이렇게 풀 생각을 하지?ㅋㅋㅋㅋ