[BOJ/py] 2304 창고 다각형

문제 링크 https://www.acmicpc.net/problem/2304

📝 문제

문제 설명
N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.

1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
2. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
3. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
4. 지붕의 가장자리는 땅에 닿아야 한다.
5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.

그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

💻 코드

N = int(input())
arr = [0] * 1001

max_height = max_idx = 0
for _ in range(N):
    idx, height = map(int, input().split())
    arr[idx] = height

    if height > max_height:
        max_height = height
        max_idx = idx

result = max_height

front = back = 0

for i in range(max_idx):
    if arr[i] <= max_height and arr[i] > front:
        front = arr[i]
    result += front

for i in range(1000, max_idx, -1):
    if arr[i] <= max_height and arr[i] > back:
        back = arr[i]
    result += back

print(result)

📌 해결방법

1. arr[idx] = height와 같은 방법으로 배열에 해당 기둥의 순서에 따라 높이를 저장
2. 넓이의 초기값을 최대 기둥으로 설정 (기둥의 너비가 1이기 때문에 넓이는 높이가 됨)
3. 최대 높이의 기둥을 기준으로 앞부분과 뒷부분을 나눠서 생각

✔ 느낀 점

처음에는 기둥의 인덱스까지 다 저장해서 더 높은 기둥이 나오면 그 인덱스의 차이만큼을 높이에 곱해서 넓이를 구하는 방식으로 구현했는데, 코드도 길어지고 더 복잡해진 것 같아서 다른 방법을 찾았다.

for문으로 한칸씩 앞으로 가면서 탐색하기 때문에 더 높은 기둥이 나오기 전까지의 기둥 높이를 계속 더하면 그게 곧 넓이가 된다!

그리고 다른 코드를 참고하니 제일 높은 기둥의 인덱스를 구할 때 arr.index(max_haight) 이런식으로 구현하면 더 편리