문제링크:https://www.acmicpc.net/problem/6549
6549번: 히스토그램에서 가장 큰 직사각형
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤
www.acmicpc.net
다루는 주제: 분할정복
import sys
def histo(arr, start, end):
if start == end:
return arr[start]
else:
mid = (start + end) // 2
width = 2 # 너비
left = mid # 경계 왼쪽
right = mid + 1 # 경계 오른쪽
min_height = min(arr[left], arr[right]) # 둘 중에 작은 값
big_square = min_height * 2 # 경계를 두고 정해지는 직사각형의 크기
while True:
if (arr[left] == 0 or left == start) and (arr[right] == 0 or right == end):
# 왼쪽, 오른쪽 경계값이 0이거나 더이상 이동할수없을떄
break
elif arr[left] == 0 or left == start: # 왼쪽으로 이동할수없을떄
if arr[right + 1] < min_height:
min_height = arr[right + 1]
right += 1
elif arr[right] == 0 or right == end: # 오른쪽으로 이동할수없을때
if arr[left - 1] < min_height:
min_height = arr[left - 1]
left -= 1
else: # 왼쪽 오른쪽 모두 이동 가능 할 경우
if arr[left - 1] > arr[right + 1]: # 왼쪽 값이 더 크고
if arr[left - 1] < min_height: # min_height 보다 값이 작으면
min_height = arr[left - 1] # min_height를 갱신해준다
left -= 1 # 다시 이동
else: # 오른쪽 값이 더 크고
if arr[right + 1] < min_height: # min_height보다 값이 작으면
min_height = arr[right + 1] # 갱신
right += 1
width += 1
big_square = max(big_square, min_height * width) # 기존의 big_square와 갱신된 넓이 비교
return max(histo(arr, start, mid), histo(arr, mid + 1, end), big_square)
while True:
square = list(map(int, sys.stdin.readline().split()))
if square[0] == 0:
break
print(histo(square, 1, len(square) - 1))
'Algorithm > 백준(파이썬)' 카테고리의 다른 글
백준 2493 파이썬(Python) 문제풀이 탑 (0) | 2023.04.19 |
---|---|
백준 10830 파이썬(Python) 문제풀이 행렬제곱 (0) | 2023.04.17 |
백준 1629 파이썬(Python) 문제풀이 곱셈 (0) | 2023.04.16 |
백준 2630 파이썬(Python) 문제풀이 색종이 만들기 (0) | 2023.04.16 |
백준 8983 파이썬(Python) 문제풀이 사냥꾼 (0) | 2023.04.16 |