BOJ 2304 : 창고 다각형 [C++]

 

2304번: 창고 다각형

 

분명 쉬운 문제인데 오래 걸렸다.

문제 분류를 보니 스택도 있던데, 나는 그냥 구현으로 해결했다.

 

1. 우선 정보를 입력받고, L(왼쪽 면의 위치)을 기준으로 오름차순으로 정렬한다.

2. 최고 높이를 가진 기둥을 찾아 그 기둥의 인덱스를 기록해 둔다.

 

3. 0부터 최고 높이를 가진 기둥의 인덱스까지 오름차순으로 검사.

3-1. 이전 최고 높이보다 높거나 같은 높이를 가진 기둥을 찾을 때마다 넓이를 정답에 더하고, H와 L을 갱신.

 

4. 마지막 인덱스부터 최고 높이를 가진 기둥의 인덱스까지 내림차순으로 검사.

4-1. 이전 최고 높이보다 높거나 같은 높이를 가진 기둥을 찾을 때마다 넓이를 정답에 더하고, H와 L을 갱신.

 

5. 정답에 가장 높은 높이를 더한다. (위 3,4번의 과정에서 최고 높이를 가진 기둥에 대한 넓이 계산을 안 했기 때문)

 

 

코드

#include <iostream>
#include <algorithm>

int N;
std::pair<int, int> bars[1001];

int main() {
    std::cin >> N;

    for (int i = 0; i < N; i++) {
        std::cin >> bars[i].first >> bars[i].second;
    }
    std::sort(bars, bars + N);
    int max_H = 0;
    int max_index = 0;
    for (int i = 0; i < N; i++) {
        if (bars[i].second > max_H) {
            max_H = bars[i].second;
            max_index = i;
        }
    }

    int answer = max_H;
    int L = 0, H = 0;
    for (int i = 0; i < max_index + 1; i++) {
        if (L == 0 && H == 0) {
            L = bars[i].first;
            H = bars[i].second;
            continue;
        }
        if (bars[i].second >= H) {
            answer += (bars[i].first - L) * H;
            L = bars[i].first;
            H = bars[i].second;
        }
    }
    L = 0, H = 0;
    for (int i = N - 1; i > max_index - 1; i--) {
        if (L == 0 && H == 0) {
            L = bars[i].first + 1;
            H = bars[i].second;
            continue;
        }
        if (bars[i].second >= H) {
            answer += (L - bars[i].first - 1) * H;
            L = bars[i].first + 1;
            H = bars[i].second;
        }
    }

    std::cout << answer << "\n";

    return 0;
}