7.4문제: 울타리 잘라내기(ID:FENCE)

문제

너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없습니다.

판자의 너비는 모두 1이라고 가정합니다.

입력

첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 판자의 수 N (1≤N≤20000)이 주어집니다. 그 다음 줄에는 N개의 정수로 왼쪽부터 각 판자의 높이가 순서대로 주어집니다. 높이는 모두 10,000 이하의 음이 아닌 정수입니다.

출력

각 테스트 케이스당 정수 하나를 한 줄에 출력합니다. 이 정수는 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기를 나타내야 합니다.

예제 출력

3
7
7 1 5 9 6 7 3
7
1 4 4 4 4 1 1
4
1 8 2 2

예제 출력

20
16
8

First Thoughts

가장 낮은 높이의 울타리 찾기

각 판자의 높이가 모두 주어지므로 주어진 판자로 만들 수 있는 최대 넓이의 직사각형은 가장 낮은 판자의 높이를 비교하며 그 넓이를 비교해야한다. 그래서 나는 2중 for문으로 범위를 정해가면서 모든 넓이를 비교해보았다.

My code

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> fence;
int max_square(vector <int>& f) {
	int i, j;
	int h = 0, w = 0;
	int p = 0;
	for (i = 0; i < f.size(); i++) {
		h = f[i];
		for (j = i; j < f.size(); j++) {
			if (h > f[j]) {
				h = f[j];
			}
			p = h * (j - i + 1);
			if (p > w) {
				w = p;
			}
		}
	}
	return w;
}
int main(void) {

	int C;
	int N;
	int h;
	cin >> C;
	for (int i = 0; i < C; i++) {
		cin >> N;
		for (int j = 0; j < N; j++) {
			cin >> h;
			fence.push_back(h);
		}
		cout<<max_square(fence)<<endl;
		fence.clear();
	}
}

Answer code

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> fence;
int solve(int l, int r) {
	if (l == r) {
		return fence[l];
	}
	int mid = (l + r) / 2;
	int ret = max(solve(l, mid), solve(mid + 1, r));
	int lr = mid, rl = mid + 1;
	int height = min(fence[lr], fence[rl]);
	ret = max(ret, 2 * height);
	while (l < lr || rl < r) {
		if (rl < r && (lr == l || fence[lr - 1] < fence[rl + 1])) {
			++rl;
			height = min(height, fence[rl]);
		}
		else {
			--lr;
			height = min(height, fence[lr]);
		}
		ret = max(ret, height * (rl - lr + 1));
	}
	return ret;
}
int main(void) {

	int C;
	int N;
	int h;
	cin >> C;
	for (int i = 0; i < C; i++) {
		cin >> N;
		for (int j = 0; j < N; j++) {
			cin >> h;
			fence.push_back(h);
		}
		cout<<solve(0,N-1)<<endl;
		fence.clear();
	}
}

Difference & Faults

시간 낭비

나의 코드의 심각한 오점은 시간문제이다. 논리적으로 오류는 없지만 2중 for문의 사용으로 효율적이지 못한 코드이다. 하지만 분할 정복을 사용하여 코드를 구현하면 훨씬 논리적이면서도 효율적인 풀이가 가능하다.

Impressions

분할 정복 알고리즘의 중요성

앞서 7.2의 쿼드 트리 문제도 하나의 문제를 여러 부문제로 분할하여 코드를 구현하였다. 이 문제 또한 결과의 경우의 수를 총 3가지로 나누어 풀이했다. 어떤 문제를 어떻게 분할할지 또 그 분할을 통해 파생되는 결과가 뭔지 정확히 파악을 해야하는 거 같다.

Summary

아이디어를 생각하기에 어려운 문제는 아니었다. 오히려 분할 정복을 어떻게 응용하여 구현할지가 고민되는 문제였다. 책에 분할 정복 알고리즘을 보니 그제서야 "분할"에 대한 이해가 됐다. 마지막 문제에서는 분할 정복을 이용하여 문제를 풀 수 있었으면 좋겠다.