[백준] 2304번 창고 다각형

사용 언어 - Python3

문제 -  2304번 창고 다각형

2304번: 창고 다각형

 

정답

누적된 숫자들의 합 prefix 응용버전 (정답 맞춘 여부 X)

1. input

입력받은 x와 y를 graph 형태로 저장해주고, x_list, y_list로 따로 리스트에 저장해준다.

가장 큰 x와 y 값을 maxHeight, maxWidth로 저장해준다.

 

2. prefix, suffix

예시 그림처럼 x가 6이었는데 그 다음 값이 3이라면 x는 6으로 유지되어야 한다.

하지만, maxHeight에 도달한다면 멈춰야 하기 때문에 양쪽으로 비교가 필요하다.

왼쪽/오른쪽부터 y값을 비교하면서 가장 큰 값으로 숫자들을 누적 기록해줄 list를 생성한다.

 

3. maxPoint

- 왼쪽부터 maxWidth까지 for문

- 오른쪽 maxWidth 부터 0까지 for문

h와 graph[f] 중 큰 값으로 prefix에 저장해준다.

prefix에는 지금까지의 합(prefix[f-1])에 현재의 막대길이(h)를 더해주면서 누적합을 구한다.

suffix에는 지금까지의 합(suffix[b+1])에 현재의 막대길이(h)를 더해주면서 누적합을 구한다.

maxHeight에 도착하면 그 값을 maxPoint에 append해주고 break

 

4. 최종 합 구하기

prefix와 suffix에는 왼쪽/오른쪽 총 막대 합이 있기 때문에 가장 큰 값을 더해준다. answer = max(prefix) + max(suffix)

maxPoint에는 최대 막대의 x 값이 두 개 있다. 

가장 큰 막대가 여러 개인 경우, 두 막대 사이는 무조건 오목하게 들어가기 때문에

그 사이 막대값은 무조건 (maxPoint[1]-maxPoint[0]+1)*maxHeight 이다. answer에 더해준다.

 

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)

 

 

레퍼런스

• 정답 깃허브

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/2304_%EC%B0%BD%EA%B3%A0%EB%8B%A4%EA%B0%81%ED%98%95.py