백준 2304 창고 다각형 파이썬 문제풀이 (python 누적합)

문제 보러가기

 

 

 

백준 창고 다각형 파이썬 문제풀이

기둥들을 가지고 가장 적은 넓이를 만드는 문제이다.

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

왔다갔다 안하고 최대한 일직선이 많은 방향으로 오목하지 않으면서 최소 넓이를 만드려면 어떻게 할까.

양쪽에서부터 최대 높이인 지점까지 양 방향으로 면적을 구하는 방법을 사용해야한다.

 

왼쪽에서부터 최대 높이까지 지점의 넓이 누적합을 구하고,

오른쪽에서부터 최대 높이까지 지점의넓이 누적합을 구한다.

 

n = int(input())
graph = [0]*10001
x_list = []
y_list = []

for i in range(n):
    x,y = map(int, input().split())
    graph[x] = y
    x_list.append(x)
    y_list.append(y)

maxHeight = max(y_list)
maxWidth = max(x_list)

prefix = [0]*(maxWidth+2)
suffix = [0]*(maxWidth+2)

maxPoint = []

h=0
for f in range(1, maxWidth+3):
    if(graph[f] == maxHeight):
        maxPoint.append(f)
        break
    h = max(h, graph[f])
    prefix[f] = prefix[f-1] + h

h = 0
for b in range(maxWidth, 0, -1):
    if(graph[b] == maxHeight):
        maxPoint.append(b)
        break
    h = max(h, graph[b])
    suffix[b] = suffix[b+1] + h

answer = max(prefix) + max(suffix)
answer += (maxPoint[1] - maxPoint[0] + 1) * maxHeight

print(answer)

사실 제대로 이해하지 못한 상태라 제대로 설명하기는 어렵다.

좀 더 노력해보자.