[BOJ 6549]

문제 바로가기 : https://www.acmicpc.net/problem/6549
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

분할 정복 문제다. 풀기에 앞서서 각 직사각형의 높이 값이 10억까지라는걸 알 수 있다.
자칫하면 int로는 오버플로우가 날 수 있기 때문에 long long으로 설정해주고 풀었다.

주어진 구간 너비가 1이 될 때까지 분할한 후 분할된 각 케이스에서 범위를 전체로 넓혀가며 값을 업데이트 한다.
구간 내 직사각형 중 가장 낮은 높이와 구간의 길이를 곱해서 반영하면 된다.
여기서 가장 낮은 높이는 height에 계속 갱신해준다. 구간[hi, lo]의 길이는 hi-lo+1이 된다.
양끝과 붙어있는 직사각형의 높이 중 큰 직사각형이 있는 쪽으로 범위를 넓혀가야 한다.

while (start < lo || hi < end) {
    if (hi < end && (lo == start || a[lo - 1] < a[hi + 1])) {
        ++hi;
        height = min(height, a[hi]);
    }
    else {
        --lo;
        height = min(height, a[lo]);
    }
    ret = max(ret, height * (hi - lo + 1) * 1LL);
}

중간(mid)을 기준으로 쪼개가며 계산만 하면 될줄 알았는데 구간이 딱 가운데만큼 잘리지는 않는다는걸 간과했다.
때문에 위와 같이 1개 단위로 남을 때까지 쪼갠 후에 범위를 확장해 나가면 모든 케이스를 체크할 수 있다.

세그먼트 트리 풀이는 여기에!