백준 2304] C++ 창고 다각형

 

 

 

 

해당 문제는 백준 사이트에서 풀 수 있습니다.

 

www.acmicpc.net/problem/2447

 

1. 문제

N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다.

이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다.

이 창고의 지붕을 다음과 같이 만든다.

 

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

그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

 

그림1 . 기둥과 지붕(굵은 선)의 예

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다.

그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

 

입력

첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다.

그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과,

높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다.

L과 H는 둘 다 1 이상 1,000 이하이다.

 

출력

첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.

 

 

예제 입력 1              7                                2 4 11 4 15 8 4 6 5 3 8 10 13 6

예제 출력 1              98

 

예제 입력 2 5 1 11 2 11 3 11 4 11 5 11

예제 출력 2 55

 

 

2. 조건

1. 기둥의 위치와 높이가 N개 만큼 주어진다.

2. 천을 기둥위에 덮으려고 하는데, 이때 파인곳 없이 천을 설치하려고 한다.

3. 예제를 보면 알다시피 천은 일자로 펴져있어 비가와도 물이 고일 수 없다.

 

 

 

3. 풀이

해당 문제는 백준의 빗물(www.acmicpc.net/problem/14719) 과 유사합니다.

 

이 문제는 어떤식으로 접근해서 문제를 풀까? 라는 문제입니다. 

 

즉, 풀이법이 정해져 있지 않은.... 구현을 간단하게 만들 수 있고, 복잡하게 만들 수 있는 그런 문제입니다.

 

저는 왼쪽 기준 총 넓이를 구하고 오른쪽 기준 총 넓이를 구해서 서로 더해줬습니다.

 

무슨말이냐??

 

 

이런식으로 빨간색 박스는 왼쪽 넓이고 노란색 박스는 오른쪽 넓이입니다.

 

왼쪽의 경우 처음 인자를 기준으로 자신 값보다 크거나 같을 때 까지 계속 찾습니다.

자신보다 큰 값이 나오면 값을 새로 갱신해주고 자기 위치부터 해당 값 위치까지의 넓이를 구해줍니다.

 

오른쪽도 마찬가지로 맨 끝 인자를 기준으로 역행하면서 자기보다 큰 값을 계속 찾습니다.

 

이런식으로 찾으면 위 예제처럼 왼쪽은 2번의 연산, 오른쪽은 1번의 연산을 진행하게 됩니다.

 

마지막으로 왼쪽 기분 가장 큰 기둥 값을 더해주면 총 넓이를 구할 수 있습니다.

(이 값은 오른쪽 기준으로 해도 같습니다.)

 

이런식으로 해준다면 모든 조건을 만족할 수 있습니다.

 

주의해야할 점은 왼쪽이든 오른쪽이든 구할 때 한쪽은 같은 값을 포함해야 한다는 점입니다.

 

 

4. 코드

#include <iostream>
#include <vector>
#include <algorithm>

#pragma warning(disable: 4996)

using namespace std;

int main() {
    int T;
    int N, M, K, H;
    int X, Y;
    int answer = 0;
    cin >> N;
    vector<pair<int, int>> v;

    for (int i = 0; i < N; i++) {
        cin >> X >> Y;
        v.emplace_back(X, Y);
    }

    sort(v.begin(), v.end(), [](auto a, auto b) {
        if (a.first < b.first) return true;
        else return false;
        });

    //왼쪽 넓이 구하기
    int left_locate = v[0].first;
    int left_MAX = v[0].second;
    
    for (auto& p : v) {
        if (left_MAX <= p.second) {
            answer += (p.first - left_locate) * left_MAX;
            left_MAX = p.second;
            left_locate = p.first;
        }
    }

    //오른쪽 넓이 구하기
    int right_locate = v.back().first;
    int right_MAX = v.back().second;
    
    for (int i = v.size() - 1; i > -1; i--) {
        if (right_MAX < v[i].second) {
            answer += (right_locate - v[i].first) * right_MAX;
            right_MAX = v[i].second;
            right_locate = v[i].first;
        }
    }
    cout << answer + left_MAX << endl;

    return 0;
}