BOJ. 1725 히스토그램 (Python)

BOJ 1725. 히스토그램

문제

https://www.acmicpc.net/problem/1725

1725번: 히스토그램

 

🔸 접근 방법

가장 큰 넓이를 가지는 직사각형을 구하기 위해서는 구간별로, 가장 작은 직사각형의 높이를 구한 후에 그 구간의 길이만큼 (가로길이) 곱해주면 된다고 생각했다.

구간별로 가장 작은 높이를 가지는 직사각형의 index값을 세그먼트 트리를 사용해서 저장했고, 분할 정복을 사용해서 가장 작은 직사각형을 사용해 넓이를 update한 후에는 각각 좌, 우 구간으로 나누어서 update를 반복했다.

 

이 과정을 정리하면 다음과 같다.

• 구간별로 가장 작은 높이 값을 가지는 직사각형의 index값 저장하기
• 전체 구간에서부터 가장 작은 직사각형의 높이값 * 그 구간의 길이를 사용해 구간에서 만들 수 있는 가장 큰 직사각형의 넓이값 구하기
• 넓이 값을 update했으면 분할정복을 사용해서 좌, 우로 구간 나눠서 넓이값 비교하기
• 전체, 좌, 우 중 가장 큰 값을 넓이 값으로 저장하기

# 1725 히스토그램
# 221002


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def init(node, s, d):
    if s == d:
        tree[node] = s
        return tree[node]

    mid = (s+d)//2
    idx1 = init(node*2, s, mid)
    idx2 = init(node*2 + 1, mid+1, d)

    if arr[idx1] < arr[idx2]:
        tree[node] = idx1
    else:
        tree[node] = idx2

    return tree[node]

# 최소 인덱스 -> 높이값 찾기
def findMin(node, s, d, l, r):
    if d < l or r < s:
        return -1

    if l <= s and d <= r:
        return tree[node]
    else:
        mid = (s+d)//2
        idx1 = findMin(node*2, s, mid, l, r)
        idx2 = findMin(node*2 + 1, mid+1, d, l, r)

        if idx1 == -1:
            return idx2
        elif idx2 == -1:
            return idx1
        else:
            if arr[idx1] < arr[idx2]:
                return idx1
            else:
                return idx2

# idx l~r 직사각형 중에서 가장 작은 index * 구간 가로 길이 (r-l+1)
def maxArea(l, r):
    if l == r:
        return arr[l]
    
    minIdx = findMin(1, 1, N, l, r)

    area = arr[minIdx] * (r-l+1)

    if l <= minIdx-1:
        area1 = maxArea(l, minIdx-1)
        if area < area1:
            area = area1
    if minIdx+1 <= r:
        area2 = maxArea(minIdx+1, r)
        if area < area2:
            area = area2

    return area

N = int(input())
arr = [0] + [int(input()) for _ in range(N)]
i = 0
while True:
    if N > 2**i:
        i += 1
    else:
        i += 1
        break

tree = [0] * (2**i)

# 세그먼트 트리에 구간별 최소 높이를 가지는 블럭의 idx 저장
init(1, 1, N)

# 정답 변수
answer = maxArea(1, N)
print(answer)

 

🔑 Key Point

🔸 값을 저장할 때, 가장 작은 높이 값을 저장하는 것이 아닌 index값을 저장해야 구간을 분할할때 써먹을 수 있다. 높이 값으로 저장하면 `.index` 를 사용해서 또 index를 찾아야한다.

🔸 분할 정복을 할때, 굳이 구간을 return해서 또 호출하지 말고 계산한 값을 불러와서 사용하니 훨씬 깔끔하게 함수를 구현할 수 있었다!

 

 

---

이 문제에 대한 풀이는 백준 블로그에 내가 사용한 분할정복, 세그먼트 트리 방식과 스택 방식 두개가 다 정리 되어있으니 그걸 참고하는 것도 추천한다.

 

 

< 백준 블로그 >

https://www.acmicpc.net/blog/view/12

히스토그램에서 가장 큰 직사각형