[Python] 백준 2304번 창고 다각형

문제

2304번: 창고 다각형

입력

• 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.

출력

• 첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.

입력 예제

7
2 4
11 4
15 8
4 6
5 3
8 10
13 6

출력 예제

98

문제 풀이

• 가장 먼저 제일 큰 높이를 찾아 그 곳의 x좌표를 기준으로 왼쪽, 오른쪽을 탐색하여 높이를 계속해서 더하면 총 면적을 구할 수 있다.
• 가장 높은 곳을 기준으로 왼쪽은 x좌표가 0인 곳 부터 가장 높은 높이 값이 있는 곳까지 높이 값을 갱신해가며 차례대로 더하고, 오른쪽은 맨 끝 좌표를 기준으로 높은곳 + 1까지 높이 값을 갱신해가며 차례대로  더한다.
• 마지막으로 이 더한 값을 출력한다. 

코드

n = int(input())
shape = []
h_list = [0 for _ in range(1001)]
for _ in range(n):
    l,h = map(int,input().split())
    h_list[l] = h
    shape.append((l,h))

# 가장 큰 높이 값 찾기
h, h_x = 0, 0
last_x = 0
for i in range(len(shape)):
    # 가장 큰 높이 구하기
    if shape[i][1] > h:
        h = shape[i][1]
        h_x = shape[i][0]

    # 마지막 x축 좌표 구하기
    if last_x < shape[i][0]:
        last_x = shape[i][0]

# 높은 곳 기준 왼쪽 탐색
result = 0
left_cur = 0
for i in range(h_x + 1):
    left_cur = max(left_cur, h_list[i])
    result += left_cur

# 높은 곳 기준 오른쪽 참색
right_cur = 0
for i in range(last_x, h_x, -1):
    right_cur = max(right_cur, h_list[i])
    result += right_cur

print(result)