[백준 2304] 창고 다각형

[백준온라인저지 2304 : 창고 다각형 ]

창고가 있는데 지붕을 씌운다.
하지만 조건이 있다!!

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

나는 그냥 입력을 기둥전부 받았고 처음에는 왼쪽에서부터 최고 높이 기둥들을 갱신하며 

답에 더해줬다.

함정은 오목한 부분이다.

만약 11~12 기둥의 높이가 9라면 

위의 그림은

이런 식으로 바뀌기 때문에 주의 해야한다. 

그래서 답을 출력하기 전에 오른쪽에서 최고 높이 기둥까지 한번 또 계산해주면서

빼주면된다..

즉흥적으로 푸는 거라 좀 복잡하게 푼 것 같다. 쉬운 다른 방법들이 많이 있을듯

#include 
int n, map[1001], ans = 0;

int main(){
 scanf("%d", &n);
 int maxy = 0, miny = 1005;
 for (int i = 0; i < n; i++){
  int a, b;
  scanf("%d%d", &a, &b);
  map[a] = b;
  if (a > maxy) maxy = a;
  if (a < miny) miny = a;
 }
 int idx = map[miny];
 for (int i = miny; i <= maxy; i++){
  if (idx < map[i])idx = map[i];
  ans = ans + idx;
 }
 if (idx > map[maxy]){
  for (int i = maxy;; i--){
   if (idx == map[i])
    break;
   else{
    if (map[i]>map[maxy]){
     ans = ans - (idx - map[i]);
     map[maxy] = map[i];
    }
    else
     ans = ans - (idx - map[maxy]);
   }
  }
 }
 printf("%d", ans);
 return 0;
}