-창고 다각형(2304)-

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
 
int pillar;
vector<pair<int, int>> pillar_information;
 
void receive_pillar_data() {
    int location;
    int hight;
 
    for(int pillar_number = 0; pillar_number < pillar; pillar_number++) {
        cin >> location;
        cin >> hight;
        pillar_information.push_back(make_pair(hight, location));
    }
    return;
}
 
//높이 기준으로 내림차순
void sort_pillar() {
    sort(pillar_information.begin(), pillar_information.end());
}
 
int make_smallest_cover() {
    int total_area = pillar_information[pillar-1].first;
    //index임
    int left_max_location = pillar_information[pillar-1].second;
    int right_max_location = pillar_information[pillar-1].second;
 
    for(int pillar_number = pillar - 2; pillar_number >= 0; pillar_number--) {
        
        //범위 안에 있을때
        if(left_max_location != right_max_location && pillar_information[pillar_number].second > left_max_location && pillar_information[pillar_number].second < right_max_location) {
            continue;
        }
        //가장 왼쪽에 있는 것으로부터 더 왼쪽에 있을 때
        else if(pillar_information[pillar_number].second <= left_max_location) {
            total_area += (left_max_location - pillar_information[pillar_number].second) * pillar_information[pillar_number].first;
            
            left_max_location = pillar_information[pillar_number].second;
        }
        //가장 오른쪽에 있는 것으로부터 더 왼쪽에 있을 때
        else if(pillar_information[pillar_number].second >= right_max_location) {
            total_area += (pillar_information[pillar_number].second - right_max_location) * pillar_information[pillar_number].first;
            
            right_max_location = pillar_information[pillar_number].second;
 
        }
    }
    return total_area;
}
 
int main() {
    int answer = 0;
        
    cin >> pillar;
 
    receive_pillar_data();
    sort_pillar();
    answer = make_smallest_cover();
    cout << answer << endl;
}

주어진 입력 자료를 sort하여 활용하면 풀 수 있는 문제였습니다.

한번에 풀 수 있는 점화식을 머리로 생각하지 말고 손으로 써가면서 경우의 수를 찾도록 해야겠습니다.