[백준 1725] 히스토그램

문제링크 : https://www.acmicpc.net/problem/1725

💻 문제 풀이 : C++

🤣 첫번째...

#include <iostream>
#include <vector>

using namespace std;

int getMax(int a, int b)
{
	return a > b ? a : b;
}

int getMin(int a, int b)
{
	return a < b ? a : b;
}

int main()
{
	long long answer = 0;
	int N;
	cin >> N;

	vector<long long> graph;
	
	for (int i = 0; i < N; i++)
	{
		long long input;
		cin >> input;
		graph.push_back(input);
	}

	int tmp = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j <= N - i; j++)
		{
			long long  minHeight = 1000000000;
			// j부터 j+i 까지 탐색
			for (int k = j; k < j + i; k++)
			{
				// 최소 높이 찾기
				if (minHeight > graph[k]) 
					minHeight = graph[k];
			}
			// 넓이 = 최소높이 * i
			answer = getMax(answer, i*minHeight);
		}
	}

	int debug = 0;

	cout << answer << endl;
	
	return 0;
}

=> 💥시간초과 !!

stack 풀이

👍 stack 풀이
https://cocoon1787.tistory.com/315

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

using namespace std;

int h[100010];

int main()
{
	int ans = 0;
	int N;
	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> h[i];

	stack<int> s;
	s.push(0);
	for (int i = 1; i <= N + 1; i++)
	{
		while (!s.empty() && h[s.top()] > h[i])
		{
			int check = s.top();
			s.pop();
			ans = max(ans, h[check] * (i - s.top() - 1));
		}
		s.push(i);
	}
	cout << ans;

	return 0;
}

분할정복 풀이

👍 JAVA but Best !
https://st-lab.tistory.com/255

#include <iostream>
#include <algorithm>
#include <stack>

#define ll long long

using namespace std;

int N;
ll h[100010];

ll getMidArea(int left, int right, int mid)
{
	int toLeft = mid;
	int toRight = mid;
	ll height = h[mid];
	ll maxAns = height;
	while (left < toLeft && toRight < right)
	{
		if (h[toLeft - 1] < h[toRight + 1])
		{
			toRight++;
			height = min(height, h[toRight]);
		}
		else {
			toLeft--;
			height = min(h[toLeft], height);
		}
		maxAns = max(maxAns, height * (toRight - toLeft + 1));
	}
	while (toRight < right)
	{
		toRight++;
		height = min(height, h[toRight]);
		maxAns = max(maxAns, height * (toRight - toLeft + 1));
	}
	while (left < toLeft)
	{
		toLeft--;
		height = min(height, h[toLeft]);
		maxAns = max(maxAns, height * (toRight - toLeft + 1));
	}

	return maxAns;
}

ll getArea(int left, int right)
{
	if (left == right)
	{
		return h[left];
	}

	int mid = (left + right) / 2;

	ll leftArea = getArea(left, mid);
	ll rightArea = getArea(mid + 1, right);
	ll midArea = getMidArea(left, right, mid);

	ll maxAns = max({ leftArea, rightArea, midArea });

	return maxAns;
}

int main()
{
	cin >> N;

	for (int i = 0; i < N; i++)	cin >> h[i];

	cout << getArea(0, N - 1);

	return 0;
}

---

📌 memo 😊