6549 히스토그램에서 가장 큰 직사각형

백준 6549 히스토그램에서 가장 큰 직사각형 :  https://bit.ly/3Jtkc86  

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

[코드 작성 전 정리]

우선 분할 정복으로 풀 것이기 때문에 재귀함수로 구현

 

필요한 것

① 반(left, right) 나누기

• return max, 높이 정보 필요 (높이는 참조로 전달)

② 합치기

• left, right 중 더 낮은 높이를 기준으로 합치기

③ 합칠 때 겹치는 부분 생각하기

• 겹치는 부분 기준으로 왼쪽, 오른쪽으로 확장하며 max값 계산하기 

 

 

 

[문제풀이]

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long


ll area(ll* his, int size, int x, ll& h) {

	if (size == 1) {
		h = his[x];
		return his[x];
	}
	else {
		// 나누기
		ll lh, rh;
		int ln = size / 2;
		int rn = size - ln;
		ll lmax = max(area(his, ln, x, lh), area(his, rn, x + ln, rh));

		//합치기
		h = min(lh, rh);
		ll tmax = h * size;

		// 겹치는 부분 확인
		int lx = x + ln - 1;
		int rx = lx + 1;
		ll th = min(his[lx], his[rx]);
		tmax = max(tmax, th * 2);

		while (lx > x || rx < x + size - 1) { 
			if (lx > x && (rx == x + size - 1 || his[lx - 1] > his[rx + 1])) { 
            // 왼쪽으로 확장 가능 && (오른쪽 끝까지 도달||오른쪽 확장 높이보다 왼쪽 확장 높이가 더 큰 경우) 
				lx--;
				th = min(th, his[lx]);
			}
			else {
				rx++;
				th = min(th, his[rx]);
			}
			tmax = max(tmax, th * (rx - lx + 1));
		}
		return max(tmax, lmax);
	}

}

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

	while (true) {
		int n;
		cin >> n;
		if (n == 0) break;

		ll* his = new ll[n];
		int k;
		for (int i = 0; i < n; i++) {
			cin >> k;
			his[i] = k;
		}
		ll h;
		ll hmax = area(his, n, 0, h);
		cout << hmax << "\n";

		delete[] his;
	}

	return 0;
}

 

ll area(ll* his, int size, int x, ll& h)
ll* his	히스토그램 높이를 저장하는 배열
int size	현재 확인하고 있는 범위
int x	현재 확인하고 있는 범위의 첫번째 인덱스 값
ll& h	현재 범위의 최소 높이 값 (전달을 위해 참조로 사용)
while문	겹치는 부분 기준으로 확장하기 위한 반복문 고려할 점 ① 현재 범위(x~x+size-1)를 벗어나지 않으면서 확장할 수 있는가 ② 왼쪽, 오른쪽 중 높이가 더 큰 쪽으로 확장할 것 ③ 한 쪽 확장이 끝나면 높이 상관없이 나머지 방향으로 확장할 것

*주의할 점

long long int 사용하기

 

[comment]

처음 분할정복 생각한게 맞았는데 괜히 다르게 푼다고 시간이 더 오래걸려서 아쉬운 문제

문제 자체는 그냥 기본 분할정복에서 겹치는 부분 고려하는 것만 추가된 느낌

추가로, 처음에 while문 작성할 때 현재 범위 한정으로 확인하고 안하고가 시간초과에 영향을 줘서 처음부터 생각하지 못한것도 아쉬움

이렇게 푼 방법 외에도 세그멘트 트리, 스택 등의 방식이 있어 추가로 풀어보는 것도 좋을 듯 싶다.