[백준] No.2304 - 창고 다각형 (C++, 스택)

문제

 

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

2304번: 창고 다각형

 

풀이

 

solved.ac 난이도: Silver 2

 

굳이 스택으로 풀지 않아도 되지만 스택으로 분류되어 있어 스택으로만 해결하려 하다 보니 코드가 복잡해진 것 같다.

 

 

일단 가장 높은 기둥(8번 기둥)의 왼쪽 부분만 생각해보자. 

만약 기둥의 높이마다 지붕을 맞춘다면

5번 기둥에서 지붕이 낮아지고 8번 기둥에서 다시 높아진다면 오목한 부분이 생겨 비가 고이게 된다.

따라서 최장 기둥의 왼쪽 부분에서 지붕은 오른쪽으로 갈수록 높아지는 경우만 허용해야 한다.

따라서 가장 높은 높이의 기둥이 나오는 위치(left_end)까지 순서대로 스택에 삽입하며 스택의 top보다 높은 기둥의 경우에만 스택에 push 해주자.

 

이번엔 가장 높은 기둥의 오른편을 생각해보자.

사실 기둥들의 좌우를 바꾸더라도 최소 다각형의 크기는 변하지 않는다. 

즉, 오른편은 오른쪽부터 왼쪽으로 계산을 진행한다면 왼쪽의 지붕을 계산하는 것과 동일하게 처리할 수 있다.

 

왼편과 오른편의 기둥들을 각각 st_left, st_right에 담았다면 

이를 아래의 함수를 호출하여 각 부분의 넓이 합을 계산해 준다.

 

 

int RoofArea(stack<pair<int,int>>& st){
  int area_sum=0;
  pair<int,int> now_pillar,next_pillar;
 
  while(st.size() >1){
    now_pillar = st.top();
    st.pop();
    next_pillar = st.top();
    area_sum += abs(now_pillar.first - next_pillar.first)*next_pillar.second;
  }
 
  return area_sum;
}
 

 

 

now_pillar은 현재 스택의 top에 위치한  기둥의 정보이고

next_pillar은 다음의 top의 기둥의 정보이다.

 

함수의 호출 전에 우리는 추가적으로 가장 높은 기둥의 정보를 각각의 스택에 삽입하여 준다.

st_left.push(v[left_end]); 

st_right.push(v[right_end]);

 

그 이유는 가장 높은 기둥의 위치와 이전의 기둥의 위치로 사각형의 너비를 계산 할 수 있기 때문이다.

 

next_pillar의 높이를 가지는 사각형의 넓이는 아래와 같다. ( first가 위치, second가 높이)

abs(now_pillar.first - next_pillar.first)*next_pillar.second

 

abs를 사용하는 이유는 오른편의 스택의 경우 now_pillar의 위치가 next_pillar의 위치보다 앞에 있기 때문이다.

 

최종적으로 가장 높은 높이(max_h)를 가지는 기둥에 의해 이루어진 지붕의 넓이를 계산하면 된다. 

왼쪽에서부터 시작해서 가장 처음 나오는 가장 높은 기둥의 위치(left_end)

오른쪽에서부터 시작해서 가장 처음 나오는 가장 높은 기둥의 위치(left_end)를 구한 이유는 이 때문이다.

 

만약 max_h의 높이를 가지는 기둥이 두 개 이상이라면

이러한 기둥 사이의 기둥들은 계산할 필요 없이 양쪽 끝의 두 기둥의 위치 너비에 max_h를 곱해주면 넓이를 구할 수 있다.

따라서 지붕의 최소 다각형의 넓이 area_sum은 아래와 같다.

area_sum += RoofArea(st_left);

area_sum += RoofArea(st_right);

area_sum += (v[right_end].first -v[left_end].first +1)* v[right_end].second;

 

코드