개요

백준 2304번: 창고 다각형

• 입력
  첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.

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

접근 방식

1. 처음에 생각했던 방식은 차례대로 탐색하면서 이전값보다 클때마다 MaxHeight변수를 갱신,
   MaxHeight변수보다 작은 값중 제일 큰 값을 secondMaxHeight이런식으로 저장해서 창고값을 구해보려 했지만, 몇 개로 나눠지는지 알수없어서 포기했다.

2. 그 다음 생각한 방식은 히스토그램 문제처럼 스택을 이용해서 막대를 처리하는 방식이였다.

3. 맨 처음 maxHeight 변수에 0을 넣는다

4. maxHeight가 0일때,

   • 이전 값보다 크다면 스택에 계속 푸시한다.
   • 이전값보다 처음으로 작아지면 maxHeight에 이전 값 넣어준 후, 스택에 푸시한다.

5. maxHeight가 0이 아닐 때,

• 이전 값보다 지금 막대가 크다면 지금 막대랑 maxHeight를 비교한다.
  -> 지금 막대가 maxHeight보다 크다면 지금막대랑 maxHeight사이의 모든 막대 pop하고
  maxHeight를 지금 막대로 갱신 및 지금 막대 스택에 푸시
  -> 지금막대가 maxHeight보다 작다면 지금 막대길이보다 작은 스택안의 막대들 다 push
  이전값보다 지금 막대가 작다면 해당 막대 푸시.
  
• 이전값보다 지금 막대가 작다면
  -> 지금 막대 push

6. 하지만 막대가 한 개만 있는 경우를 고려를 안했고, 계속 100퍼에서 오답이 떴다.
   이 부분을 못 찾아서 결국 인터넷과 질문게시판을 검색했다.

코드

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

using namespace std;

int N=0;
vector<pair<int, int>> v;
stack<pair<int,int>> s;

bool comp(pair<int,int> a, pair<int,int> b) {
	if (a.first != b.first) return a.first < b.first;
	//물론 a와 b의 위치가 같을일은 없지만 엄격하게 비교함수 작성해야하므로
	else return a.second < b.second;

}

void input() {
	int L = 0, H = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> L >> H;
		v.push_back(make_pair(L, H));
	}
	sort(v.begin(), v.end(), comp);

}
/// <summary>
/// 입력값들을 stack안에 조건에 맞게 넣는 함수
/// </summary>
void roofStackManage() {
	int tmpIndex = 0, tmpHeight = 0, maxHeight = 0;
	//정렬된 입력값들 순서대로 스택에 넣고 빼는 작업
	for (int i = 0; i < v.size(); i++)
	{
		tmpHeight = v[i].second;
		tmpIndex = v[i].first;
		//맨 처음
		if (i == 0)
		{
			s.push(make_pair(tmpIndex, tmpHeight));
			continue;
		}

		//지금 막대가 스택의 top 막대보다 크다면 
		if (v[i].second >= s.top().second) {
			//한번도 밑으로 안꺾인 막대그래프면
			if (maxHeight == 0) {
				//그대로 push
				s.push(make_pair(v[i].first, v[i].second));
				continue;
			}
			//지금까지 제일 큰 높이보다 크다면
			else if (v[i].second >= maxHeight) {
				//해당 높이 값 다음 막대들 다 스택에서 pop
				while (s.top().second != maxHeight) {
					s.pop();
				}
				//maxHeight 갱신
				maxHeight = v[i].second;
				s.push(make_pair(v[i].first,v[i].second));
				continue;
			}
			//한번 꺾인 애면 지금 넣으려는갑보다 낮은 막대들 전부 pop
			while (s.top().second <= v[i].second) {
				s.pop();
			}
			//막대 넣기
			s.push(make_pair(v[i].first, v[i].second));
		}
		//지금 넣으려는 막대가 스택의 top 막대보다 작다면
		else {
			maxHeight = max(maxHeight,s.top().second);
			s.push(make_pair(v[i].first, v[i].second));
		}

	}
}

/// <summary>
/// stack안에 조건에 맞게 들어간 막대들을 통해 지붕 넓이 구하는 함수
/// </summary>
void calculateRoofArea() {
	int tmpIndex=0, tmpHeight=0,retArea=0;
    //s.size()가 1일때를 고려안했더니 답이 0이 나온다.
	if (s.size() == 1) {
		cout << s.top().second;
		return;
	}
	while (!(s.size()==1)) {
		tmpIndex = s.top().first;
		tmpHeight= s.top().second;
		s.pop();

		//만약 해당 값보다 이전 값이 크다면 
		if (s.top().second >= tmpHeight) {
			retArea += (tmpIndex - s.top().first) * tmpHeight;
			//계산하고 스택 size가 1일땐 스택 top것도 계산해줘야함 마지막 막대는 무조건 작대기 하나.
			//(마지막 남은게 평평해지려면 평평해진 값 끝값 두개 들어가있어야해서 모순)
			if (s.size() == 1) {
				retArea += s.top().second;
			}
		}
		//만약 해당 값보다 이전 값이 작다면
		else {
			retArea += tmpHeight;
			retArea += (tmpIndex - s.top().first-1) * s.top().second;
			if (s.size() == 1) {
				retArea += s.top().second;
			}
		}
	}
	cout << retArea;
}


int main() {
	input();
	roofStackManage();
	calculateRoofArea();
}

생각

반례를 찾아 떠돌아다니며 본 팁인데, 백준에서 높은 퍼센트에서 오답을 맞으면
적은 범위의 답을 시도해보라고 했다.