[백준 2034번] 파이썬-창고 다각형

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

2304번: 창고 다각형

 

# 조건

N개의 막대 기둥, 폭은 1m 높이는 다를 수 있음
지붕은 모두 연결되어야하고, 수평부분은 반드시 기둥의 윗면과 닿아야함
수직은 기둥의 옆면과 닿아야함
가장자리는 땅에 닿아야하고 지붕의 어떤 부분도 오목하게 들어가지 않는다.

 

# 접근방법

1. 지붕의 어떤 부분도 오목하게 들어가지 않으므로 지금 높이의 지붕보다 낮은 기둥이 온다면 무시해도 된다.

2. 따라서 각 높이에 대한 배열을 만들어 준 후, 나보다 높은 숫자를 만나기 전까지 내 값을 복사해주면 된다.

3. 가장 높은 기둥을 기준으로 좌측은 -> 방향, 우측은 <- 방향으로 넓이를 가르쳐 주었다.

4. 넓이를 구하는 문젠데 높이를 구한이유 = 사각형의 넓이는 결국 각 행의 높이를 더해주는 것과 같기 때문이다!!

 

# 기둥 개수
N = int(input())
# 가장 높은 길이와 인덱스, 가장 끝에 있는 번호와 그 때의 높이를 구해준다.
pillar = []
highest = 0
longest = 0
highest_idx = 0
longest_height =0
for i in range(N):
    a,b = map(int, input().split())
    # 왼쪽 면과 높이를 각각 리스트에 넣어준다.
    pillar.append((a,b))
    if b > highest:
        # 가장 높을 때의 인덱스
        highest = b
        highest_idx = a
    if a > longest:
        # 가장 끝에 있는 기둥 번호와 높이
        longest = a
        longest_height = b
#print(highest_idx, highest, longest_height, longest)
# 가장 높은 곳을 기준으로 좌측, 우측으로 나눠서 해준다.
sum = 0
# 높이 기록해줄 배열
arr=[0]*(longest+1)
nopi = 0
# 각 번호에 맞는 높이 기록
for i in range(len(pillar)):
    arr[pillar[i][0]] = pillar[i][1]

# 가장 높은 곳 기준 좌측
for j in range(1,highest_idx):
    # 다음 높이가 이전 높이보다 낮아면, 이전 높이로 통일
    if not arr[j] > arr[j-1]:
        arr[j] = arr[j-1]
# 우측
for k in range(longest, highest_idx, -1):
    # 왼쪽 높이가 오른쪽보다 낮아면 오른쪽높이로 통일
    if not arr[k-1] > arr[k]:
        arr[k-1] = arr[k]

for l in arr:
    sum += l

print(sum)