📒 문제
N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.
- 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
- 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
- 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
- 지붕의 가장자리는 땅에 닿아야 한다.
- 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.
그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.
그림1 . 기둥과 지붕(굵은 선)의 예 - https://www.acmicpc.net/problem/2304
창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.
기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.
입력
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.
출력
첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.
✏️ 풀이
처음 풀기 시작했을 때는, 가장 높은 바 이전, 이후로 나뉘어서 각각의 넓이를 구하고 모든 합을 구하는 방법을 생각했었다. 하지만 코드를 적어나가다보니, 넓이를 구하는 방법이 제각각이 되는 부분이 생기게 되어 if문의 반복이 많아지고 코드가 복잡해지는 것을 알 수 있었다.
따라서 이 방법을 포기하고, 가장 높은 바의 왼쪽, 오른쪽으로 나눠서, 그림 1처럼 좌표를 생각하고 이를 리스트로 구현하여 각각의 값들을 더해나가는 방법을 생각해보았다.
N = int(input())
bar_list = []
for i in range(N):
bar_list.append(list(map(int, input().split())))
bar_list = sorted(bar_list, key = lambda x: x[0])
maxi_x, maxi_y = 0, 0
for i in range(len(bar_list)):
if maxi_x < bar_list[i][0]:
maxi_x = bar_list[i][0]
if maxi_y < bar_list[i][1]:
maxi_y = bar_list[i][1]
grid = [0] * (maxi_x + 1)
for x, y in bar_list:
grid[x] = y
result = 0
tmp = grid[0] # 가장 큰 값의 왼쪽 부분
for i in range(grid.index(maxi_y)+1):
if tmp < grid[i]:
tmp = grid[i]
result += tmp
tmp = grid[-1] # 가장 큰 값의 오른쪽 부분
for i in range(len(grid)-1, grid.index(maxi_y), -1):
if tmp < grid[i]:
tmp = grid[i]
result += tmp
print(result)위의 방법으로 메모리는 29200kb, 시간은 120ms로 적당한 결과를 얻을 수 있었다.
