[n2304] 창고 다각형 - 파이썬

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

2304번: 창고 다각형

(문제)

창고 다각형의 면적이 가장 작은 창고를 구하는 문제

 

지붕을 만드는 규칙

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

 

---

(처음 생각)

이것도 좀 전에 풀었던 문제(색종이2- 2567)처럼 똑같은 방식으로 푸는건가 했다.

그런데, 아무리 생각해봐도 너무 비효율적인 방식이고

복잡해서 .. 그냥 다른 방법을 구상해냈다.

 

---

(풀이)

가장 최고 높이인 기둥의 위치를 미리 구한다.

그 기둥을 기준으로 왼쪽과 오른쪽으로 나눠서 생각해야 한다.

왼쪽, 오른쪽 모두 최대 높이의 기둥보다 작은 기둥만 존재한다.

 

(왼쪽 탐색)

: 2번 기둥의 높이 4를 maxCheck 변수에 넣고,

더 높은 기둥이 나타날때까지는 maxCheck 값을 더해준다.

 

 

 

(오른쪽 탐색)

하지만 오른쪽 부분에서 많이 헤맸다.

왼쪽 부분에서 해온 방향대로 하게 되면,

오목하게 들어간 부분이 생기기 때문이다.

 

따라서 오른쪽 부분에서는왼쪽에서 해온 방향(왼쪽->오른쪽)을 바꿔서(오른쪽->왼쪽)으로 탐색해야 오목한 부분이 생기지 않는다.

 

 

다각형의 면적이 가장 작게 하라고 했으니까

위와 같은 방식으로 해야 한다.

 

num = int(input())
row_max, col_max = 0, 0
array = [[0, 0] for i in range(1001)]

for i in range(num):
    x, y = map(int, input().split())
    row_max = max(x, row_max)  # x 최댓값 = 마지막 기둥 위치.
    col_max = max(y, col_max)  # y 최댓값 = 기둥 높이 최댓값
    array[x] = [x, y]

maxCheck = 0
max_idx = 0

for i in range(1, row_max + 1):
    if array[i] != 0:
        if array[i][1] == col_max:
            max_idx = i

result = 0

for i in range(1, max_idx):
   # 가장 높은 기둥 왼쪽편 = 계속 더해준다
    maxCheck = max(maxCheck, array[i][1])
    result += maxCheck

maxCheck = 0
for i in range(row_max,max_idx,-1):
    # 가장 높은 기둥 오른쪽 편
    maxCheck = max(maxCheck, array[i][1])
    result += maxCheck

print(result+col_max)

 

 

일단 기둥의 개수가 최대 1000개까지니까,

1001로 배열 범위를 잡았다.

 

입력값을 보면 알 수 있지만,

기둥이 있는 위치의 정보만 주기 때문에

기둥이 비어있는 곳은 [0,0]으로 초기화해줘야한다고 생각했다.

 

입력값에서 x,y 를 받으면

인덱스 x번째에 [x,y] 입력값을 넣는다.

 

maxCheck는 최댓값 체크하는 변수

max_idx는 최댓값 인덱스

 

for문을 이용해서 max_idx를 구해줬다.