26 Aug 2020

[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개 단위로 남을 때까지 쪼갠 후에 범위를 확장해 나가면 모든 케이스를 체크할 수 있다.

예전에 [단계별로 풀어보기 - 분할 정복]에서 봤던 첫 플래티넘 문제였는데 어떻게 풀지 머리를 싸매다 포기했던 기억이 난다.
종만북에서 어디서 많이 본 문제같아 찾아보니 똑같은 문제였다! 여기서도 분할 정복 문제에 속해 있었다.
알고리즘 분류에 세그먼트 트리가 있어서 이걸로는 풀 수 있지 않을까 찾아봤는데 되게 복잡해 보여서 이것도 포기했었다ㅋㅋㅋ
간만에 본 기념으로 오기로 세그먼트 트리로 풀어보려고 했는데 세그먼트 트리도 사실상 divide and conquer고 .. 음..
위 풀이를 함수로 만들어서 클래스에 추가만 된 상태라 코드만 길어졌다! 업로드는 여기에!

Location

Icheon, KR

Email

iteratively@naver.com

Social

-->