[BOJ] 2304. 창고 다각형 Python

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

2304번: 창고 다각형

 

 

1. 해결방법

솔직히 개인적으로 접근 하는 데 있어서 너무 어려웠다...

엄청 많은 시간이 투자해도 해결하지 못해서 다른 분들의 힌트를 보고 해결했다,,,,,,

위 문제는 stack으로도 해결해도 되지만, 조건이 너무 까다로워서 stack으로 해결하지 못했다.

핵심포인트는 가장 높이가 큰 인덱스의 정보를 찾고, 왼쪽과 오른쪽 끝에서 부터 탐색하면서 넓이를 구하는 것이다
왼쪽부터 보면, 4 + 4 + 6 + 6 + 6 + 6 까지 진행될 것이다. 높이가 커진 부분을 갱신해가면서 해결하면 된다.

 

 

2. 정답코드

import sys

input = sys.stdin.readline

N = int(input())

max_H = 0
max_L = 0
max_H_index = 0
numbers = []
for _ in range(N):
    L, H = map(int, input().split())
    numbers.append([L, H])

    if H > max_H:
        max_H = H
        max_H_index = L

    if L > max_L:
        max_L = L

targetList = [0] * (max_L + 1)
for l, h in numbers:
    targetList[l] = h

w = 0

# 왼쪽에서 더하기
temp = 0
for i in range(max_H_index + 1):
    if targetList[i] > temp:
        temp = targetList[i]

    w += temp

# 오른쪽에서 더하기
temp = 0
for i in range(max_L, max_H_index, -1):
    if targetList[i] > temp:
        temp = targetList[i]

    w += temp

print(w)