백준 BOJ 6198 - 옥상 정원 꾸미기

USACO

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

6198번: 옥상 정원 꾸미기

N이 8만으로 크기 때문에

O(N^2) 시간복잡도를 가지는 프로그램으로는 이 문제를 해결할 수 없다.

 

풀이가 떠오르지 않아서, stack 자료구조를 사용한다는 힌트를 태그 분류를 통해 얻고 시작했다.

 

기존의 K번 빌딩에서 볼 수 있는 빌딩 옥상의 개수를 확인하려면,

K보다 큰 인덱스에 대해 탐색을 해야 하는데,

문제를 거꾸로 뒤집어서 K번 빌딩"을" 볼 수 있는 빌딩들의 개수

로 보면 해답에 더 쉽게 다가갈 수 있다.

 

K번 빌딩을 볼 수 있는 빌딩의 조건은

1. K번 빌딩보다 왼쪽에 있을 것.

2. K번 빌딩보다 높을 것.

3. K번 빌딩과의 사이에 같거나 더 높이가 높은 빌딩이 없을 것.

 

이 세가지 조건을 모두 만족해야 한다.

이를 위해서,

스택에 빌딩의 높이를 저장해주면서 1번 조건을 충족시키고,

스택에 본인보다 낮은 높이의 빌딩이 없도록 값을 조절해가면서 스택을 관리하면

2번 조건과 3번 조건을 충족시킬 수 있으며,

이때 스택에 남아있는 빌딩들의 높이는 점점 감소하는 꼴이 된다.

 

또한, 이렇게 만들어진 스택의 크기가 곧

K번 빌딩을 볼 수 있는 빌딩들의 개수이기 때문에,

이를 전부 더해주면 AC를 받을 수 있다.

 

정답은 int범위를 초과할 수 있으므로

long long 형을 사용하도록 하자.

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
using namespace std;

stack<int> s;
int arr[87654] = {0};

int main(){
	int N;
	long long ans = 0;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> arr[i];
	}
	
	for(int i=0; i<N; i++){
		while(!s.empty() && s.top() <= arr[i]){ s.pop(); }
		ans += s.size();
		s.push(arr[i]);
	}
	
	cout << ans;
	return 0;
}