[Algorithm] 백준 6549번: 히스토그램에서 가장 큰 직사각형 | 분할 정복 응용

문제 출처: https://www.acmicpc.net/problem/6549

---

1. 결과

메모리 44580KB, 시간 3468ms

2. 풀이

우선 풀었을 때, 첫 플래티넘 문제라는 것이 신기하고 좋았다. 분할 정복법의 큰 틀에서 벗어나지 않은 형식인 것 같은데, 의외로 난이도가 있었다는 이야기 같다. 말한 대로 이 문제는 재귀를 통한 분할 정복법을 이용한다. 주어진 높이 리스트를 반을 가른 후, 그 반의 왼쪽에 있는 높이들 중에서 가장 큰 넓이, 반의 오른쪽에 있는 높이들 중 가장 큰 넓이, 그리고 가운데 선을 포함하여 가장 큰 넓이를 각각 구한다. 그리고 이 셋 중 가장 큰 넓이를 반환하면 된다.

왼쪽과 오른쪽의 높이들에는 다시 이 함수를 재귀로 적용시키면 된다. 이 문제의 등급을 플래티넘으로 올리는데 한 몫한 것은 가운데 선을 포함한 넓이 계산 부분인 것 같다. 우선 결국 가운데 선을 포함하기 때문에 가운데 선 바로 왼쪽과 바로 오른쪽 높이는 기본으로 깔고 간다. 두 높이 중 낮은 높이에 맞춰야 하기 때문에, 초기 넓이는 이 중 낮은 높이에 2를 곱한 값이다. 이후 각각 서로 더 왼쪽, 더 오른쪽에 있는 높이를 비교한 후, 그나마 높이가 높은 쪽으로 영역을 넓혀가는 방식으로 각 경우의 넓이를 계산한다. 그리고 틈틈이 이 넓이를 비교하여 최대 넓이를 저장하는 변수도 선언해둬야 한다. 그리고 만약 모든 높이가 다 똑같아서 한쪽 방향으로만 인덱스가 몰린 경우도 있다. 나는 높이가 왼쪽이 크거나 같으면 왼쪽 높이를 선택, 아니면 오른쪽을 선택하는 방식으로 구현했기 때문에 1000, 1000, 1000, 1000과 같은 케이스가 주어지면 3000에서 종료되었다. 이를 해결하기 위해 왼쪽과 오른쪽 인덱스를 가리키는 변수 범위를 0과 n으로 했고, 만약 0이 되는 쪽은 이후 높이를 0으로  저장되도록 했다. 이렇게 함으로써 한쪽이 높거나 같아서 끝나도, 결국 모든 영역을 계산해보도록 했다. 이렇게 구한 값과 재귀로 구한 좌우 높이까지 비교해서 최댓값을 반환했다.

오히려 다른 골드 문제보다 수월하게 풀린 느낌이 있지만, 방심하지 말고, 자만하지 말고 어떤 문제든 최선을 다해서 풀자.

import sys

def getRect(heights):
    n = len(heights)
    if n == 1: return heights[0]
    mid = n // 2
    left_h = getRect(heights[:mid])
    right_h = getRect(heights[mid:])
    l = mid - 1
    r = mid
    under_w = 2
    min_h = min(heights[l], heights[r])
    max_area = under_w * min_h
    
    while 0 <= l and r + 1 <= n:
        lh = heights[l-1] if l >= 1 else 0
        rh = heights[r+1] if r < n-1 else 0
        min_h = min(min_h, lh) if lh > rh else  min(min_h, rh)
        if lh > rh: l -= 1
        else: r += 1
        under_w += 1
        max_area = max(max_area, under_w * min_h)
    
    return max(left_h, right_h, max_area)

def main():
    while True:
        heights = list(map(int, sys.stdin.readline().split()))
        if len(heights) == 1 and heights[0] == 0: break
        print(getRect(heights[1:]))

if __name__ == "__main__":
    main()