[BOJ] 6198 옥상 정원 꾸미기 (C++)

1. 문제 링크

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

 

2. 문제 접근

- 개인적으로 문제는 Stack으로 풀면 쉽게 풀리는 것을 깨닫기가 어렵다.

- Stack까지 생각해냈다면, 그 뒤에는 Stack의 특징을 잘 이용해서 풀 수 있다.

- 왼쪽 건물에서 오른쪽 건물을 볼 수 있으려면 반드시 빌딩의 높이가 더 낮아야 한다.

- 즉,  오른쪽 건물 중에 자신보다 높은 건물이 하나 등장하면, 이 건물이 더 이상 확인 가능한 건물은 없다.

- 이를 잘 이용하면 stack을 이용해서 풀 수 있다.

 

- 처음 10을 넣을때는 바로 넣는다. 3을 넣을때는 3이 10보다 작다.

- 즉, 10의 관점에서는 3을 볼 수 있기 때문에 값을 1증가한다.

- 7을 넣을때는 7이 3보다 크기 때문에, 3을 빼내고 넣어준다. 

- 이때, 7도 10과 비교해야 한다. 7이 10보다 작다.

- 즉, 10의 관점에서는 7을 볼 수 있기 때문에 값을 1증가한다.

 

- 4의 경우는 7까지만 비교를 해도 된다. (뒷 값은 7보다 클 것이 확실하기 때문에 말이다.)

- 즉, 2만큼 더해주면 된다.

 

3. 문제 풀이

- stack이 비어있는 경우엔 그냥 넣는다.

- stack이 현재 건물보다 작은 건물이 stack에 있다면 모두 pop() 처리한다.

- stack의 top에 현재 건물보다 큰 건물이 존재한다면, push()하기 전에 해당 스택의 크기 만큼 증가 시킨다.

(top에 있는 건물이 현재 건물보다 크다면, 그 안에 있는 건물들은 무조건 현재 건물보다 클 것이기 때문이다.)

 

4. 소스 코드(C++)

#include <iostream>
#include <stack>
using namespace std;
stack<int> value;
int main(void)
{
	int n;
	long long int answer = 0;

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int temp;
		cin >> temp;
		while (!value.empty() && value.top() <= temp) // 현재 건물보다 작은게 있으면 pop.
		{
			value.pop();
		}
		if (!value.empty() && value.top() > temp) // 현재 건물보다 큰 건물이 있으면 그 건물들은 현재 건물의 옥상을 볼 수 있음.
		{
			cout << "size : " << value.size() << std::endl;
			answer += value.size();
		}
		value.push(temp);
	}
	cout << answer;
}