[백준] 6198번 옥상 정원 꾸미기

www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

꼭 기억해놓으면 좋을 것 같은 방식이다. 스택에서 말고도 여기저기 많이 쓰여서 몇번 찾아서 다시 봤는데도 암기가 잘 안되서 그냥 외우겠다는 마인드로 정리한다.

 

아이디어는 다음과 같다. (스택함수가 아닌 배열을 스택식으로 사용했다.)

여러개의 건물이 있을 때 N번째의 건물을 볼 수 있는 것은 N번째 이전의 건물 중 N번째보다 높은 건물만 N번째를 볼 수 있다. (같아도 안됨)

따라서 N번째 이전에 존재하는 N번째 건물보다 높이가 같거나 낮은 건물은 순서대로 제거한다. (N번째 건물로 인해 뒤에 건물을 볼 수 없으므로 결과값에 영향을 미칠 수 없다.)

앞의 결과물로 존재하는 건물의 배열(스택)의 높이는 내림차순으로 존재하게 된다.

sum의 값에 N번째 이전의 건물의 개수를 더한다.

N + 1번째 건물에 대해 위의 과정을 반복한다.

 

N : 건물의 개수

pos : 새로운 건물의 높이를 입력 받을 때 까지 배열에 존재하는 건물의 개수(=위치)

 

//6198
#include <iostream>

using namespace std;

const int MX = 80005;
int dat[MX];
int pos = 1;

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(NULL);
	int N, cnt = 0;
	long long sum = 0;
	int buf;

	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> buf;

		while (pos != 1 && dat[pos - 1] <= buf)
			pos--;

		sum += (long long)(pos - 1);
		dat[pos] = buf;
		pos++;
	}
	cout << sum;

	return 0;
}