백준 12846(무서운 아르바이트)스택

https://www.acmicpc.net/problem/12846

 

무조건 연속해서 일을 하고, 일한 날 중에서 일급이 가장 낮은 날을 기준으로 급여를 받는다. 

단순하게 완전탐색으로 n^2의 시간이 걸리게 풀 수 있다. 

 

겨울 스터디 모의고사때 오기로 계속 틀렸던 기억이난다. 

 

하지만 시간이 1초로 불가능했고, 1초안에 풀려면 세그먼트 트리랑 스택으로 풀어야한다고 한다.

 

이 문제는 가장 큰 히스토그램 문제와 일치하는 문제이다. (백준 6549)

https://www.acmicpc.net/problem/6549

 

스택으로 구현하는 것은 단순 이것을 위한 알고리즘이라는 느낌이 마구 들어서 이걸 이용해서 다른 어떤 것으로 응용이 가능할지는 모르겠다.

 

스택에 pair로 위치와 높이를 저장한다. 

 

조건을 걸어서 넣고 빼고를 하는 단순한 생각하기 힘든 문제이다.

 

스택의 top에 있는 값보다 높이가 크면 그냥 저장, 작으면 여러 조건을 따져서 넓이를 계산한 뒤 끝.

마지막으로 남아있는 스택의 값들에 대해서 계산 후 종료

 

현재 index보다 앞선 index중 현재의 height보다 큰 height로 이루어진 모든 직사각형에 대해서 계산을 하고,

(이 과정에서 stack에는 높이가 오름차순으로 저장되게 된다.)

 

계산 완료된 높이를 더 작은 현재의 높이로 변경. 

n까지 계산 후 아직 남아있는 높이에 대해서 계산.

 

이렇게 세 단계로 나눌 수 있는 것 같다. 

 

 

아래는 

 

7

4 3 2 4 4 5 1로 코드 구현 알고리즘 과정

 

 

 

 

 

#include<iostream>
#include<stack>
#include<utility>
#include<vector>
using namespace std;

int n, a, tmp_i;
long long ans = 0, tmp;
stack<pair<int, int> > st;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
		
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		if (st.empty()) st.push(make_pair(i, a));
		else {
			if (st.top().second < a) {
				st.push(make_pair(i, a));
			}
			else if (st.top().second > a) { 
				while (!st.empty() && st.top().second > a) { //stack에 있는 현재 높이보다 큰 높이에 대해서 넓이 계산
					tmp = st.top().second * (i - st.top().first);
					tmp_i = st.top().first;
					st.pop();
					if (tmp > ans) ans = tmp; //최댓값 갱신
				}
				st.push(make_pair(tmp_i, a)); //모두 조사 후에 더 작았던 높이로 히스토그램 다시 만들기
			}
		}
	}
	while (!st.empty()) { //stack에 남아있는 높이에 대해서 계산하는 과정
		tmp = st.top().second * (n - st.top().first);
		st.pop();
		if (tmp > ans) ans = tmp;
	}
	cout << ans << "\n";


}