백준 6198 옥상 정원 꾸미기

작성일 | In |

Problem : 옥상 정원 꾸미기

유형 : 스택

문제 설명

도시에는 N개의 빌딩이 있다.
빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.
i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.
i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, …. , N이다.
그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

1
2
3
4
5
6
7
8
             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호
  • 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
  • 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
  • 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
  • 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
  • 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
  • 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

예제 입력

첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

1
2
3
4
5
6
7
6
10
3
7
4
12
2

예제 출력

각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

1
5

해결 전략

bad hair day 문제이다.
A빌딩 앞에, 더 높은 B 빌딩이 서버리면
A빌딩의 관리자는 은 더 이상 옥상을 확인할 수 있는 빌딩이 존재하지 않는다.
앞의 B빌딩이 다 가려버리기 때문이다. A빌딩은 앞으로 의미가 없어진다.

만약 A빌딩 보다 B빌딩이 작다면,
B빌딩을 stack에 추가하기 전의 stack size는 B빌딩을 볼 수 있는 관리자의 수이다.

주의할 점

  • 없음

풀이

새로운 빌딩과 스택 top의 빌딩을 비교한다.

  • 새로운 빌딩이 더 크거나 같다면, 이제 top은, 더이상 볼 수 있는 옥상이 없어진다.
    • 새로운 빌딩이 다 가려버리기 때문이다.
    • top에 있는 빌딩은 이제 쓸모가 없으므로 stack에서 제거해준다.
  • 새로운 빌딩이 더 작다면, 스택안에 있는 빌딩들은 모두 새로운 빌딩보다 큰 빌딩들이다.
    • 스택안의 모든 빌딩들은 새로운 빌딩을 볼 수 있게된다.
    • 새로운 빌딩을 추가하기전 스택의 사이즈만큼 답에 더한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
#define ll long long
using namespace std;

stack<int> s;
int n;
ll answer;

void view_check(ll building) {
	while (!s.empty()) {
		if (building >= s.top())s.pop();
		else {
			answer += s.size();
			return;
		}
	}
}

void solve() {
	ll building;
	while (n--) {
		cin >> building;

		if (!s.empty()){
			if (building < s.top()) answer += s.size();
			else view_check(building);
		}
		s.push(building);
	}
	cout << answer;
}

void input() {
	cin >> n;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//freopen("input.txt", "r", stdin);

	input();
	solve();
	return 0;
}

피드백

없음