[C++] 백준 2304번: 창고 다각형

문제

https://www.acmicpc.net/problem/2304
Olympiad > 한국정보올림피아드 > KOI 2005 > 초등부 2번
초등부문제라는 게 날 자극한다..

풀이

웅덩이가 없으려면 5 2 6 처럼 높은 곳에서 아래로 내려갔다가 다시 올라가면 안된다는 조건이 있어야 한다.

높이의 max를 구해 반으로 가르고 -> , <- 나눠 총 넓이를 구했다.

소스

#include <iostream>

int main()
{
    int N =0, L =0, H=0, area =0;
    int pillars[10001];
    int left =10001, right =0, max = 0; // position

    std::cin >> N;
    for(int i =0; i<N; ++i)
    {
        std::cin >> L >> H;
        pillars[L] = H;
        if(pillars[L] > pillars[max]) max = L;
        if(left > L) left = L;
        if(right < L) right = L;
    }

   // -> max
    int height = pillars[left], pos = left;
    for(int i = left+1; i <= max; ++i)
    {
        if(pillars[i] >= height)
        {
            area +=(i-pos)*height;
            pos = i;bheight = pillars[i];
        }
    }
    
	// max <-
    height = pillars[right]; pos = right;
    for(int i = right-1; i >= max; --i)
    {
        if(pillars[i] >= height)
        {
            area +=(pos-i)*height;
            pos = i; height = pillars[i];
        }
    }
    std::cout << area + pillars[max];
    return 0;
}