[c++] 백준 6549 - 히스토그램에서 가장 큰 직사각형

0. [c++] 백준  -

https://www.acmicpc.net/problem/6549

1. 풀이

1) 분할정복을 활용하여, [left,mid], [mid+1,right] 두 구간으로 나누고 각 구간의 최댓값과, 두 구간을 겹친 경우를 찾아보는 알고리즘을 구현하였다.

시간복잡도는 O(nlgn)으로 구현되었다.

처음에 int로 구현하여 범위 초과로 인해 한번 틀리고 long long으로 바꾸어 선언하였다. string이나 배열을 활용하여 다시금 구현하려 했었는데, 다행히 금방 수정할 수 있었다.

2) 추가적으로 모든 경우를 계산하는 코드도 참고적으로 올려본다.

2. 소스코드

1) 분할 정복을 활용한 풀이

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include<vector> #include<iostream> #include<algorithm>   using namespace std;   //각 판자의 높이를 저장하는 배열 vector<long long> h; //h[left..right] 구간에서 찾아낼 수 있는 가장 큰 사각형의 넓이를 반환한다. long long solve(int left, int right) {     //기저 사례: 판자가 하나밖에 없는 경우     if (left == right) return h[left];     //[left,min], [mid+1,right]의 두 구간으로 문제를 분할한다.     int mid = (left + right) / 2;     //분할한 문제를 각개격파     long long ret = max(solve(left, mid), solve(mid + 1, right));     //부분 문제 3: 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다.     long long lo = mid, hi = mid + 1;     long long height = min(h[lo], h[hi]);     //[mid,mid+1]만 포함하는 너비 2인 사각형을 고려한다.     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 N,temp;     cin >> N;     while (N) {         h.clear();         for (int i = 0; i < N; i++) {             cin >> temp;             h.push_back(temp);         }         cout << solve(0, N - 1) << endl;         cin >> N;     } } Colored by Color Scripter

cs

2) 모든 방법을 전부 확인하는 풀이

1 2 3 4 5 6 7 8 9 10 11 12 13

int bruteForce(const vector<int>& h) {     int ret = 0;     int N = h.size();     //가능한 모든 left, right 조합을 순회한다.     for (int left = 0; left < N; left++) {         int minHeight = h[left];         for (int right = left; right < N; right++) {             minHeight = min(minHeight, h[right]);             ret = max(ret, (right - left + 1)*minHeight);         }     }     return ret; } Colored by Color Scripter

cs

3. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.197~201.

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!