백준 6549 히스토그램에서 가장 큰 직사각형
문제 설명
- 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다.
- 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수 있다.
- 각 테스트 케이스에 대하여 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하라.
입력 값
- 입력은 테스트 케이스 여러 개로 이루어져 있다.
- 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음 주어진다.
( 1 <= n <= 100,000 )
- 그 다음 n 개의 정수 h1, ... hn ( 0 <= hi <= 1,000,000,000)이 주어진다.
이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽 순서대로 주어진다.
- 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.
예제
문제 분석
- 이 문제는 히스토그램의 최대 넓이를 구하는 문제이다.
- 단순하게 생각해보면, 왼쪽에서 부터 시작하는 모든 히스토그램의 넓이를 살펴보면,
모든 히스토그램의 넓이를 알 수 있다.
- 이 경우에는 시간 복잡도는 N+(N-1)+(N-2)+...+1 이 되기 떄문에 O($N^2$)이 된다.
즉, 불가능해진다.
- 그렇다면 어떻게 접근해야 할까?
- 이 문제는 분할 정복으로 접근해야 한다.
- 주어진 배열의 중간 값인 mid를 구한다.
- 이때 주어진 배열에 의해 히스토그램을 만드는 경우 최대가 나오는 경우의 수는
- start ~ mid 안에 있거나, mid+1 ~ last 안에 있거나 mid를 통과하는 것 중 하나이다.
- 즉, 이 문제는 중간 값을 기준으로 나눈 두 부분과 중간 값을 지나는 히스토그램 중 최대를 찾으면 된다.
- 두 부분으로 나누는 것이 logN, 다시 합치는 것이 logN이고
- 합치는 과정에서 중간 값을 통과하는 히스토그램을 찾아야 하는 과정이 N이 소요된다.
- 이 경우의 시간 복잡도는 O(NlogN)이 된다.
소스 코드
#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;
long long rec(int start, int last, vector<int> &v) {
if (start == last) {
return v[start];
}
long long result = 0;
int mid = (start + last) / 2;
int left = mid;
int right = mid + 1;
long long height = min(v[left], v[right]);
result = height * 2;
while (start < left || right < last) {
long long now = 0;
// 왼쪽 끝
if (left == start) {
right++;
now = v[right];
}
// 오른쪽 끝
else if (right == last) {
left--;
now = v[left];
}
// 다음 선택할 인덱스의 값 중 큰 값으로 이동한다.
else if (v[left - 1] > v[right + 1]) {
left--;
now = v[left];
}
else {
right++;
now = v[right];
}
height = min(height, now);
result = max(result, height*(right - left + 1));
}
result = max(result, rec(start, mid, v));
result = max(result, rec(mid + 1, last, v));
return result;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, H;
cin >> N;
while (N != 0) {
vector<int>v;
for (int i = 0; i < N; i++) {
cin >> H;
v.push_back(H);
}
cout << rec(0, N - 1, v) << endl;
cin >> N;
}
return 0;
}
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
[BOJ-10282] 해킹 (0) | 2021.07.30 |
---|---|
[BOJ-10026] 적록색약 (0) | 2021.07.29 |
[BOJ-4991] 로봇 청소기 (C++) (0) | 2021.07.27 |
[BOJ-4195] 친구 네트워크 (C++) (0) | 2021.07.26 |
[BOJ-2629] 양팔저울 (C++) (2) | 2021.07.20 |
댓글