백준-6189 (골드 5) 옥상 정원 꾸미기 STACK

해당 문제의 알고리즘 분류를 보면 스택을 사용하여야 한다고 되어있습니다.

 

만약 배열을 써서 계속 반복문을 돌려도 풀 수 있을거 같긴한데 시간초과가 날꺼 같았습니다.

 

해당 문제에 입력이 아래 처럼 나온다면

6
10
3
7
4
12
2

 

처음에 스택은 비어있기 때문에  0을 증감 시키고 10을 스택에 추가합니다.

3은 10보다 작기 때문에 while문을 돌지 않고 스택의 사이즈만큼 증가시키고 3을 스택에 추가합니다.

 

count : 1

 

현재 스택 : [10,3] 

 

다음으로 7이 입력으로 들어옵니다. 7은 3보다 크기 때문에  while문을 돌고 증가 후 스택에 7을 추가합니다.

 

counnt: 2

 

현재 스택 : [10,7]

 

4가 들어옵니다 while문을 돌지 않고 증가시키고 4를 추가합니다.

 

count: 4

 

현재 스택 : [10,7,4]

 

12가 들어옵니다 스택안에 있는 숫자는 12보다 작기 때문에 스택이 empty가  됩니다  그리고 스택에 12를 추가합니다

 

count: 4;

 

현재 스택 : [12]

 

2가 들어옵니다 2는 12보다 작기 때문에 스택의 크기만큼 증가 시키면  카운트가 5가 됩니다.

 

 

여기서 스택의 크기를 더하는 이유는 스택이 10, 7 , 4 일때  4는 7보다도 작고 10보다도 작으니
그 스택의 크기만큼 더해야 합니다. 

 

 

#include <iostream>
#include <stack>


using namespace std;




int main() {
	
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	stack<long long> st;
	
	long long count = 0;
	
	long long n,x;
	
	cin >> n;
	
	for(int i = 0; i < n; i++){
		cin >> x;
		
		
		while(!st.empty() && st.top() <= x){
			st.pop();
		}
		
		count += (long long)st.size();
		st.push(x);
	}
	
		
	
	 
	
	cout << count;	
	

	
}