[C++][백준 1725] 히스토그램

문제

접근 방법

히스토그램에서 가장 큰 직사각형을 풀었다면 바로 풀 수 있을 것이다. 같은 문제이지만 차이점이 2개 존재한다. 첫 번째로는 출력이 int의 범위라는 것을 명시해준 것, 두 번째로는 테스트케이스가 여러 개가 아니란 것이다.

세그먼트 트리로 영역별 가장 낮은 높이의 인덱스를 저장해주고 가장 낮은 높이부터 넓이를 구해가며 분할 정복하면 되는 문제이다.

코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> nums, tree;
int N, ret = 0;
int init(int start, int end, int node)
{
    if (start == end)
        return tree[node] = start;
    int mid = (start + end) / 2, nextNode = node * 2;
    int leftIdx = init(start, mid, nextNode), rightIdx = init(mid + 1, end, nextNode + 1);
    return tree[node] = (nums[leftIdx] > nums[rightIdx] ? rightIdx : leftIdx);
}
int find(int start, int end, int node, int left, int right)
{
    if (start > right || end < left)
        return -1;
    if (start >= left && end <= right)
    {
        return tree[node];
    }
    int mid = (start + end) / 2, nextNode = node * 2;
    int leftIdx = find(start, mid, nextNode, left, right), rightIdx = find(mid + 1, end, nextNode + 1, left, right);
    if (leftIdx == -1)
        return rightIdx;
    else if (rightIdx == -1)
        return leftIdx;
    else
        return (nums[leftIdx] > nums[rightIdx] ? rightIdx : leftIdx);
}
void partSolve(int left, int right)
{
    if (left > right)
        return;
    int idx = find(0, N - 1, 1, left, right);
    int area = (right - left + 1) * nums[idx];
    ret = ret > area ? ret : area;
    partSolve(left, idx - 1);
    partSolve(idx + 1, right);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        int num;
        cin >> num;
        nums.push_back(num);
    }
    tree = vector<int>(N * 4);
    init(0, N - 1, 1);
    partSolve(0, N - 1);
    cout << ret;
    return 0;
}

풀이

똑같은 문제이기에 어렵지 않게 풀었다. 이 문제는 출력이 int 형임을 명시해주었기에 굳이 long long 같은 형식을 사용해줄 필요는 없어 보인다.