https://www.acmicpc.net/problem/2304
문제
> N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다.
> 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다.
창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.
1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
2.지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
3.지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
4.지붕의 가장자리는 땅에 닿아야 한다.
5.비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.
> 그림 1은 창고를 옆에서 본 모습을 그린 것이다.
이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다.
이 다각형을 창고 다각형이라고 하자.
> 창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다.
그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.
> 기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.접근
문제의 그림을 보면 넓이를 구하기 위해선 가장 높은 기둥을 기준으로 왼쪽과 오른쪽으로 나누어서 두 면적을 더하고 가장 높은 기둥의 넓이를 더해주면 된다.
그리고 가장 왼쪽과 가장 오른쪽의 기둥이 기준이 되고 이 기둥들 보다 작은 기둥은 고려되지않고 넘어가다가 더 높은 기둥이 나오면 지붕이 높이가 변화하며 기준기둥이 바뀐다.
즉, 면적을 구하기 위해선, 가장 높은 기둥을 찾아 이를 기준으로 왼쪽 오른쪽 나눠서 가장 왼쪽기둥부터 증가시키며 만약 왼쪽 기둥보다 큰기둥이 나타나면 해당 기둥에서 왼쪽 기둥의 x값을 빼고 높이를 곱해 면적을 구해주고, 새로 잡은 기준기둥 또한 더 높은 기둥을 만나면 x좌표를 뺴고 높이를 곱해 면적을 더해준다. 이 과정을 하며 가장 높은 기둥까지 간다.
오른쪽도 이와 마찬가지로 기둥을 감소시키며 더 높은 기둥을 탐색하고 만나면 면적구하고 기준 기둥을 갱신해준다.
위는 이제 가장 높은 기둥이 하나일 때만 생각한거고 만약 가장 높은 기둥이 여러개면 최대 높이를 먼저 구하고 그 높이와 같은, 가장 높은 기둥을 다 구해 인덱스를 찾는다.
여기서 아무리 기둥이 여러개 나온다고 해도 결국 필요한건 가장 높은기둥 중 제일 왼쪽(가장 작은 인덱스), 제일 오른쪽 기둥(인덱스가 마지막)이다. 이 둘을 기준으로 둘 사이에 어떤 기둥이 있다고 한들 얘네보다 작거나 같아서 그냥 둘의 x좌표의 차이 +1(기둥 하나의 두께더해줘야 면적에 공백이 안생김) * 높이 해주면 된다.
문제해결
> 먼저 기둥의 개수와 기둥의 위치,높이를 쌍으로 입력받아 벡터에 저장한다. 입력을 받음과 동시에 가장 높은 기둥의 길이를 미리 잡아놓는다.
> 이제 기둥을 나열해 면적을 구하기위해 기둥의 x좌표를 기준으로 작은것부터 오름차순으로 정렬해 나열한다.
> 기둥을 순회하며 최대 높이와 같은 기둥의 인덱스를 찾아 Maxindex()벡터에 넣는다. 하나일 수 도 있고, 여러개일 수도 있다.
> 창고의 면적을 담을 size와 면적계산을 위한 가장 왼쪽기둥의 위치와 높이를 wfront, hfront로 가져온다.(기준기둥을 잡는다)
> 이제 다음기둥(1번인덱스 기둥)부터 가장 왼쪽에있는 제일 높은 기둥까지 순회를 하며 더 높은 기둥이 나오면 기준기둥의 좌표를 갱신해주고 해당 기둥까지의 면적을 계산한다.
오른쪽 부분도 위와 마찬가지이고 인덱스만 끝부터 --해주며 순회한다.
> 이제 위에서 구한 면적과 가장 높은 기둥간의 면적을 더해줘야 최종 면적이므로 최고기둥간 면적을 구한다.
Maxindex.back()과 Maxindex[0]으로 기둥의 인덱스를 잡고 이 인덱스를 stick(기둥 벡터)에 넣어.first로 기둥의 x좌표를 가져온다. 두 값을 빼주고 면적에 공백이 생기지 않게 1을 더해준뒤 높이값 Hmax를 곱해준다.
> 여기서 만약 기둥이 하나 뿐이었다면 back에 대한 인덱스와 [0]에 대한 인덱스가 동일하므로 결국 +1만남아 제대로 면적이 구해진다.
또 기둥이 각각 왼쪽끝, 오른쪽끝에 존재하는경우에도 위의 좌우 탐색 반복문의 범위가 성립하지않아 면적이 구해지지않고 이 명령문에서 전체의 면적이 처리되어 구해진다.
즉, 모든 예외가 처리된다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b)
{
return a.first < b.first;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
int Hmax = 0; // 젤 높은 기둥의 높이
vector<pair<int, int>> stick(N); // 기둥x,y좌표로
for (int i = 0; i < N; i++)
{
cin >> stick[i].first >> stick[i].second;
Hmax = max(stick[i].second, Hmax); //입력받으면서 가장 높은 기둥 높이 구하기
}
sort(stick.begin(), stick.end(), cmp);//x좌표 위치로 정렬
vector<int> Maxindex;
for (int i = 0; i < N; i++) //젤 높은 기둥의 인덱스 찾기
{
if (stick[i].second == Hmax) Maxindex.push_back(i); //젤 높은 기둥이 여러개 일때
}
int size = 0;
int Hfront = stick[0].second; //최좌측 기둥의 y좌표(길이)
int Wfront = stick[0].first; //최좌측 기둥의 x좌표
for (int i = 1; i <= Maxindex[0]; i++) //두번째 기둥부터 최좌측기둥과 비교, 가장 높은 기둥의 첫번째 기둥까지
{
if (stick[i].second > Hfront) //다음기둥높이가 커야만 사이즈 계산
{
size += (stick[i].first - Wfront) * Hfront; //다음기둥이 더높다.
Hfront = stick[i].second;
Wfront = stick[i].first;
}
}
Hfront = stick[N-1].second;
Wfront = stick[N-1].first;
for (int i = N-2; i >= Maxindex.back(); i--)
{
if (stick[i].second > Hfront)
{
size += (Wfront - stick[i].first) * Hfront;
Hfront = stick[i].second;
Wfront = stick[i].first;
}
}
size += (stick[Maxindex.back()].first - stick[Maxindex[0]].first + 1) * Hmax;
cout << size << '\n';
}
후기
처음에 예외에 대해서 기둥이 하나일때, 기둥이 하난데 왼쪽끝, 오른쪽 끝에 각각 있을때, 두개이상일 때, 또 두개이상인데 각각끝에 있을 때를 다 나눠서 조건문 처리해서 했는데 끝이없었다. 그래서 일단 다 그려서 나열해놓고 보니 규칙이 보였고 그 규칙이 마지막 최고높이 기둥간 면적을 구해주는 부분에서 대부분 처리가 가능했다.
구조를 세우고 하는게 이렇게 중요하다.
