[백준 2304] 창고 다각형 [Java]

문제

2304번: 창고 다각형

---

풀이

문제에서 주어진 5번 조건에 따라 기둥과 기둥사이에는 오목하게 들어간 부분 없이 가장 작은 창고 다각형의 면적을 구해야 한다. 때문에 이 문제는 가장 큰 높이의 기둥의 위치( divL ) 중심으로 문제를 분할할 수 있다.

 

기둥의 순서가 무작위지만, L의 최대가 1000이므로 선형 계산은 오래 걸리지 않는다.

입력받은 기둥들에 대한 정보를 배열에 기록해주면서 divL을 구하자. 

 

이제 왼쪽 끝 기둥부터 divL까지, 오른쪽 끝 기둥에서 divL + 1까지 각각 ASC으로 현재 최대 기둥의 높이( curH )를 갱신하며, 더해주면 된다.

왼쪽 끝 ~ divL 까지의 기둥에 대한 면적계산이 끝났다면, curH를 초기화해주자.

 

알고리즘 분류에 Stack이 적혀있지만,  실버2라는 난이도에 비해 Stack을 적용하기가 더 어려운 풀이가 될 것으로 예상된다. (입력의 순위가 무작위이고 크기가 1000으로 매우 작다. 또한, Stack으로 두 기둥에 대한 L을 받아와 차만큼 H를 곱하는 로직이 더 복잡하기 때문)

---

소스코드

보기