[백준/2304] 창고 다각형 (Python)

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

2304번: 창고 다각형

 

Difficulty : Silver 2

 

Status : Solved

 

Time : 00:13:00

 

---

 

문제 설명

 

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

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

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

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

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

 

입력 및 출력

 

입력

첫 줄에는 기둥의 개수를 나타내는 정수 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

 

---

 

풀이

 

최소 창고 다각형을 달성하려면, 다음 그림과 같은 지붕 형태가 되어야 한다.

구체적으로, 최고 높이 기둥을 기준으로 왼쪽은 오름차순으로, 오른쪽은 내림차순으로 지붕 높이가 결정되는 형태이다. 여기서 각 부분 넓이는 (이전 최고 높이) * (이전과 현재 구간의 차)가 된다.

 

• make_polygon : 최고 높이까지 오름차순으로 진행하며 부분 넓이를 더해주는 함수이다. 최고 높이 좌표까지 도달하면 부분 넓이를 반환한다.
• solve : 메인함수. 만약 기둥이 1개뿐이라면 최고 높이를 반환한다. 그렇지 않다면 make_polygon으로 오름차순 부분과 내림차순 부분 넓이를 구한다. 총 넓이는 이렇게 구한 좌측 부분 넓이 + 우측 부분 넓이 + 중앙 최고 넓이 (1 X 최고 높이 = 최고 높이)가 된다. 기둥 리스트는 좌표를 기준으로 정렬되어야 한다는 전제조건이 붙으며, 우측의 내림차순 넓이는 이러한 기둥 리스트를 reverse하면 바로 구할 수 있다.

 

 

 

풀이 코드

 

N = int(input())
col_list = [list(map(int, input().split())) for _ in range(N)]
col_list.sort()

max_coord, max_height = max(col_list, key = lambda x : x[1])

def make_polygon(lst) :
  result = 0
  prev_coord, prev_height = lst[0]
  
  for coord, height in lst[1:] :
    if coord == max_coord :
      result += abs(coord - prev_coord) * prev_height
      return result
    if height > prev_height :
      result += abs(coord - prev_coord) * prev_height
      prev_coord, prev_height = coord, height
  
  return result

def solve() :
  if N == 1 :
    print(max_height)
    return

  left_polygon = make_polygon(col_list)
  right_polygon = make_polygon(list(reversed(col_list)))
  print(left_polygon + right_polygon + max_height )

solve()

풀이 완료!