[백준] 2304번 창고 다각형 _ 문제 풀이

 


1. 문제

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

2. 풀이

N = int(input())
cols = []
for _ in range(N):
    cols.append(list(map(int,input().split())))
cols.sort(key=lambda x: x[0])

# 최대 col 찾기
max_idx = cols.index(max(cols, key=lambda x: x[1]))
answer = cols[max_idx][1]
# 왼쪽. 맨 왼쪽에서부터 최대 인덱스까지 자신과 크기가 작은 얘들은 무시하고, 크거나 같은 얘를 만나면 지붕을 세움
this_idx = 0
for idx in range(1, max_idx+1):
    if cols[this_idx][1] <= cols[idx][1]:
        answer += cols[this_idx][1]*abs(cols[idx][0]-cols[this_idx][0])
        this_idx = idx
# 오른쪽. 맨 오른쪽에서부터 출발하면 왼쪽과 동일한 로직으로 문제 해결 가능
this_idx = -1
for idx in range(len(cols)-2, max_idx-1, -1):
    if cols[this_idx][1] <= cols[idx][1]:
        answer += cols[this_idx][1]*abs(cols[idx][0]-cols[this_idx][0])
        this_idx = idx
print(answer)