[Coding Test][Python][백준] BOJ #2304 창고 다각형

#2304 창고 다각형

문제)

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

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

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

 

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

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

입력)

첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다.

그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.

출력)

첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.

---

풀이)

※ 풀이 아이디어

"오목한 부분이 없도록" 하는 최소 면적의 다각형을 구해야한다.
즉, 왼쪽에서 오른쪽으로 가장 높은 기둥으로 가면서 기둥의 높이가 증가하고, 가장 높은 기둥에서 오른쪽 기둥으로 갈수록 기둥의 높이가 낮아야합니다.

1. 기둥을 위치 순으로 정렬
2. 왼쪽 기둥 -> 가장 높은 기둥까지 면적 계산
    2.1) 현재 기둥 > 다음 기둥 : 현재 기둥 높이를 유지, (위치 차이 * 현재 기둥 높이)만큼 면적 추가 
    2.2) 현재 기둥 < 다음 기둥 : (위치 차이 * 현재 기둥 높이)만큼 면적 추가, 현재 기둥의 높이를 다음 기둥의 높이로 갱신 
3. 가장 높은 기둥 <- 오른쪽 기둥 면적 계산(역방향으로 탐색)
    3.1) 현재 기둥 > 다음 기둥 : 현재 기둥 높이를 유지, (위치 차이 * 현재 기둥 높이)만큼 면적 추가 
    3.2) 현재 기둥 < 다음 기둥 : (위치 차이 * 현재 기둥 높이)만큼 면적 추가, 현재  기둥의 높이를 다음 기둥의 높이로 갱신 
4. 가장 높은 기둥의 면적 추가

 

문제의 예제 Input에서 케이스를 모두 확인하기 위해서 오른쪽에 기둥 하나를 더 추가한 그림입니다.

 

 

① : 2.2)의 상황입니다. (현재 높이 * 위치 차이)의 면적만큼 더하고, 다음 기둥의 높이로 갱신합니다

② :2.1)의 상황입니다. 빗물이 고이지 않게 하기 위해 (현재 높이 * 위치 차이) 만큼의 면적을 더하고, 높이 갱신은 하지 않습니다.

③ : 2.2)의 상황이지만 위치 차이는 (8 - 5)가 됩니다.

④ : 3.1)의 상황입니다. 현재 기둥 높이를 유지, (위치 차이 * 현재 기둥 높이)만큼 면적 추가합니다. 위치 차이가 위치 15의 위치와 계산하는 것이 아닌 13, 11간의 차이를 사용하면서 합하게 됩니다.

⑤ : 3.2)의 상황입니다. 위치 차이 * 현재 기둥 높이)만큼 면적 추가, 현재  기둥의 높이를 다음 기둥의 높이로 갱신 

N = int(input())

# 가장 높은 막대를 기준으로
# 왼쪽은 오른쪽으로 갈수록 높이가 높아져야하고, 오른쪽은 왼쪽으로 갈수록 높이가 높아져야한다.
# 오목한 부분을 안만들기 위해서

bars = []
max_height, max_height_idx = 0, 0

for i in range(N):
    loc, height = map(int, input().split())
    bars.append([loc, height])

# x축 기준으로 정렬
bars.sort(key=lambda x : x[0])

# 기둥의 최대 높이와 그 Index 찾기
for i in range(N):
    if bars[i][1] > max_height:
        max_height = bars[i][1]
        max_height_idx = i

# 가장 높은 기둥  
res = max_height

# 왼쪽에서 오른쪽으로 면적 계산
curr_height = bars[0][1]

for i in range(max_height_idx):
    # 다음 기둥이 현재 기둥보다 높으므로 현재 기둥의 높이만큼의 면적을 더해준다
    # 현재 기둥의 높이는 갱신
    if curr_height < bars[i+1][1]:
        res += curr_height * (bars[i+1][0] - bars[i][0])
        curr_height = bars[i+1][1]   
    else:
        # 다음 기둥이 현재 기둥 보다 낮다
        # ==> 현재 기둥의 높이만큼의 면적만 더해준다
        res += curr_height * (bars[i+1][0] - bars[i][0])


# 오른쪽에서 왼쪽으로 면적 계산
curr_height = bars[-1][1]

for i in range(N-1, max_height_idx, -1):
    if curr_height < bars[i-1][1]:
        res += curr_height * (bars[i][0] - bars[i-1][0])
        curr_height = bars[i-1][1]   
    else:
        res += curr_height * (bars[i][0] - bars[i-1][0])

print(res)