[PS] BOJ 6549 / 히스토그램에서 가장 큰 직사각형
![[PS] BOJ 6549 / 히스토그램에서 가장 큰 직사각형](/content/images/size/w2000/2025/09/-------------11.png)
문제 링크: https://www.acmicpc.net/problem/6549
분할 정복으로 풀면 됩니다.
풀이
분할 정복 (Divide & Conquer)
분할 정복이란, 어떤 큰 문제를 작은 문제들로 계속 쪼갠 뒤 그 답을 합쳐서 전체 문제의 답을 계산하는 방법입니다.
이 문제의 경우도, 답을 구하려는 히스토그램의 범위를 절반씩 쪼개면서 풀고 그 답을 합칠 수 있습니다.
문제 분할하기
먼저, 답을 구하려는 범위를 $(s, e)$라고 합시다. $N$개의 히스토그램 막대를 각각 0번부터 $N-1$번이라고 할 때, 전체 문제의 범위는 $(0, N-1)$이 됩니다.
이 범위를 반씩 쪼개서 부분 문제로 만들고, 부분 문제를 풀어 그 답을 구합니다.
만약 쪼개진 부분 문제의 범위 $(s, e)$가 $s = e$인 경우, $s$번째 막대의 높이 heights[s]를 반환하고 종료합니다. (재귀 종료 조건)
HEIGHT_LIMIT = 1_000_000_001
heights = [0] * 100_000
def divide_and_conquer(s, e):
# Divide
if s == e:
return heights[s]
mid = (s + e) // 2
left_surface = divide_and_conquer(s, mid)
right_surface = divide_and_conquer(mid + 1, e)문제 분할하기
분할한 문제의 답 합치기
def divide_and_conquer(s, e):
... (분할 코드)
... (투 포인터 코드)
# Conquer (Combine)
return max(answer, left_surface, right_surface)부분 문제의 답 합치기
앞서 전체 문제의 범위 $(s, e)$를 반으로 쪼개, 그 중심인 $m = (s + e) / 2$을 기준으로 $(s, m)$과 $(m + 1, e)$의 2개의 부분 문제로 나눠 그 답을 구했습니다.
이제, 분할한 문제의 답을 합쳐 전체 문제의 답을 구해야 합니다. 단순히 두 부분 문제 $(s, m)$과 $(m + 1, e)$의 답 중 더 큰 쪽을 고르면 될까 싶지만, 두 구간에 모두 걸치는 직사각형의 경우 아직 계산에 포함되지 않았습니다.
따라서, 투 포인터 기법을 활용해 전체 범위 $(s, e)$에서 직사각형의 넓이를 다시 계산해 줍니다. 이후 두 부분 문제 $(s, m)$, $(m + 1, e)$의 답과 투 포인터로 계산한 $(s, e)$ 내부의 가장 큰 직사각형의 넓이 중 가장 큰 것이 답이 됩니다.
투 포인터
투 포인터란, 한 개의 반복문에서 2개의 변수를 조절하며 배열과 같은 특정 구간을 탐색하는 방법입니다. 2중 반복문으로 돌면 $O(N^2)$이지만, 투 포인터의 경우 $O(N)$으로 탐색할 수 있습니다.
왼쪽 구간 $(s, m)$과 오른쪽 구간 $(m + 1, e)$에서 구할 수 있는 직사각형의 최대 넓이는 앞서 부분 문제를 통해 구했으니, 이제 두 구간 모두에 걸치는 직사각형의 넓이를 계산해야 합니다. 따라서 2개의 포인터를 구간의 중앙에서 시작해 양쪽으로 넓혀가며 계산하도록 구현했습니다.
포인터의 왼쪽 끝 $l$은 $m$, 오른쪽 끝 $r$은 $m + 1$에서 시작해 양 끝의 두 막대 중 더 높이가 높은 쪽으로 범위를 넓혀가며, 직사각형의 넓이를 계산합니다.
(단, 전체 구간 $(s, e)$를 벗어나지 않게 조절합니다.)
이 때, 직사각형의 넓이는 (범위 내 막대의 높이의 최솟값) × (현재 두 포인터에 포함된 막대의 개수) 이며, 범위 내 막대의 높이의 최솟값을 $h$이라 할 때 $h \times (r - l + 1)$로 표현할 수 있습니다.
포인터를 늘려서 새 막대를 포함했을 때, 이전의 넓이보다 오히려 작아질 수도 있으므로 기존에 계산한 넓이와 비교해 더 큰 쪽을 답으로 사용해야 합니다.
def divide_and_conquer(s, e):
... (분할 코드)
# 투 포인터
min_height = HEIGHT_LIMIT
answer = 0
l = mid
r = mid + 1
while s <= l and r <= e:
min_height = min(min_height, heights[l], heights[r])
answer = max(answer, min_height * (r - l + 1)) # 기존에 구한 최대 면적과 현재 범위 내의 최대 면적 중 최댓값 사용
if l == s:
r += 1
elif r == e:
l -= 1
elif heights[l - 1] < heights[r + 1]:
r += 1
else:
l -= 1
# 정복 (Conquer 또는 Combine)투 포인터로 (s, e) 내부의 직사각형 넓이 계산하기
전체 코드
input = open(0).readline
HEIGHT_LIMIT = 1_000_000_001
heights = [0] * 100_000
def divide_and_conquer(s, e):
if s == e:
return heights[s]
mid = (s + e) // 2
left_surface = divide_and_conquer(s, mid)
right_surface = divide_and_conquer(mid + 1, e)
min_height = HEIGHT_LIMIT
answer = 0
l = mid
r = mid + 1
while s <= l and r <= e:
min_height = min(min_height, heights[l], heights[r])
answer = max(answer, min_height * (r - l + 1)) # 기존에 구한 최대 면적과 현재 범위 내의 최대 면적 중 최댓값 사용
if l == s:
r += 1
elif r == e:
l -= 1
elif heights[l - 1] < heights[r + 1]:
r += 1
else:
l -= 1
return max(answer, left_surface, right_surface)
while True:
hist_text = input().rstrip()
if hist_text == "0":
break
hist = map(int, hist_text.split())
N = next(hist)
for i, h in enumerate(hist):
heights[i] = h
print(divide_and_conquer(0, N - 1))solution.py