BOJ 6198] 옥상 정원 꾸미기

문제 바로가기

 

접근법

하나의 빌딩은 오른쪽 방향에 있는 빌딩만 볼 수 있다. 한 방향으로만 진행되므로 스택을 이용하면 좋을 것 같다고 생각함.

 

1. 빌딩의 높이를 저장하는 스택(빌딩[])과, 순서를 저장하는 스택(시퀀스[]) 두가지를 이용한다.

2. 첫번째 입력값을 두가지 스택에 일단 푸쉬한다.

3. 두번째 빌딩의 높이가 주어지면, 빌딩 스택의 top과 비교한다.

3-1. 만약 top <= 입력값이면, 빌딩 스택을 pop하고 시퀀스 스택의 값을 이용해서 볼 수 있는 빌딩의 개수(result)를 저장한다.

3-2. 만약 top > 입력값이면,  빌딩 스택과 시퀀스 스택 모두 저장한다.

4. 모든 데이터가 스택에 저장되서 끝나게 되면, 남은 스택의 개수 만큼 result를 증가시킨다.

 

 

[코드 보기]

 

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

using namespace std;

stack<long long> s;
stack<long long> sequence;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long n, temp, num;
	cin >> n;
	num = n;
	long long res=0;

	for (long long i = 0; i < n; i++) {
		cin >> temp;
		if (i == 0) {
			s.push(temp);
			sequence.push(num--);
		}
		else {
			if (s.top() <= temp) {
				while (!s.empty() && s.top() <= temp) {
					s.pop();
					res += (sequence.top() - num - 1);
					//cout << "res : " << res << "\n";
					sequence.pop();

					
				}
				s.push(temp);
				sequence.push(num--);
			}
			else {
				s.push(temp);
				sequence.push(num--);
			}
		}

		
	}


	if (s.size() > 1) {
		
		while (!sequence.empty()) {
			res+=(sequence.top() - num - 1);
			sequence.pop();
		}
	}
	
	cout << res;
	 
	 return 0;
}

 

 

[시행착오]

1. 스택에 남아있는 것들도 카운팅 해주어야 함.

2. push된 순서를 저장하고, 이를 이용해서 값을 구하려면 큰값 - 작은값 으로 해야한다.