(c++) BOJ 6549번 분할 정복

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

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

 

 

---

 

 

문제 개요

 

 

여러 가지 풀이가 존재하는 문제지만

분할 정복으로 해결하는 방법으로 풀었다.

 

히스토그램이 주어졌을 때 분할 정복으로 구간을 나누어 계산한다.

2로 나누어 왼쪽, 오른쪽, 가운데 세 구간에 대한 경우를 구하면 된다.

 

1. 왼쪽에 최대 값 직사각형이 만들어 질 때

2. 오른쪽에 최대 값 직사각형이 만들어 질 때

3. 가운데 부분을 걸쳐서 최대 값 직사각형이 만들어 질 때이다.

 

1번과 2번은 분할 정복으로 쉽게 구해지지만

 

3번은 가운데에서 왼쪽이나 오른쪽으로 한 칸씩 이동했을 때 더 큰 값이 나오는 경우를 찾아주면 된다.

 

 

코드

 

 

n이 100,000

직사각형 최대 크기가 1,000,000,000이기에 최대값을 구하는 변수에는 long long 선언해야 한다.

 

코드 이해나 알고리즘 이해는 했는데, 메모리 초과와 시간 초과가 많이 나왔었다.

 

배열 선언과 입력부분을 살펴보고

 

변수 n을 받는 위치를 살펴보도록 하자

(cin >> n; 위치만 아래와 같이 바꾸었더니 메모리 초과가 해결되었다... 이유까지는 모르겠다.)

 

#include <bits/stdc++.h>

using namespace std;

// 높이 저장 배열
vector<long long> h;

long long solve(int left, int right) {
    if (left == right) return h[left];
    int mid = (left + right) / 2;
    // 분할 정복
    long long ret = max(solve(left, mid), solve(mid+1, right));
    int le = mid, ri = mid + 1;
    // 직사각형의 높이는 선택된 곳에서 가장 작은 것
    long long height = min(h[le], h[ri]);
    // mid, mid+1이 최대인 경우
    ret = max(ret, height * 2);
    while (left < le || ri < right) {
        // 높이가 큰 쪽으로 확장
        if (ri < right && (le == left || h[le-1] < h[ri+1])) {
            // 오른쪽이 높이가 클 때
            ++ri;
            // 가장 작은 높이 선택
            height = min(height, h[ri]);
        }
        else {
            // 왼쪽이 높이가 클 때
            --le;
            // 가장 작은 높이 선택
            height = min(height, h[le]);
        }
        // 사각형 넓이
        ret = max(ret, height * (ri - le + 1));
    }
    return ret;
}

int main(void) {
    int n, a;
    cin >> n;
    while (n != 0) {
        h.clear();
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;
            h.push_back(a);
        }
        cout << solve(0, n-1) << '\n';
        cin >> n;
    }
    return 0;
}