[백준: 6198] 옥상 정원 꾸미기

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

6198번: 옥상 정원 꾸미기

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

이런 문제이다.

 

즉 자신보다 낮은 빌딩은 확인하고 그때의 갯수가 카운트 되지만 자신보다 높으면 확인하지 막히는 문제이다.

 

입출력 예제를 보고 생각을 해보자

예제 입력 1 복사

6
10
3
7
4
12
2

예제 출력 1 복사

5

 

즉 첫번째에 N을 입력받고 차례대로 층의 수가 입력이 된다.

이때

10층은 3, 7, 4를 볼 수 있으니 = 3

3층은 막혀있음 = 0

7층은 4층을 확인 할 수 있으니 = 1

4층은 막혀있음 = 0

12층은 2층을 확인 할 수 있으니 = 1

2층은 끝이라서 막혀있음 = 0

3 + 1 + 1 = 5로 출력이 5가 나오는 것을 확인 할 수 있다. 

 

즉 이후에 추가되는 값을 확인한 후 카운트 하여 구할 수 있을거라고 생각 했다.

 

정리하면

1. 아파트의 개수 n 입력
2. 처음 기준이 되는 층이 리스트에 들어감
3. 순회하면서 기준이 되는 요소(가장 높은 층)을 기준으로 확인하여 작은 층을 체크 후 pop을 하여서 기존의 큰 건물만 남겨둔다 그렇게 길이는1로  result += 1 해준다.
4. 이때 다음요소보다 작은 요소가 있을 수 있으니 위에서 pop 했던 요소를 다시 push
5. 그렇게 순환되어 총 갯수가 나오게 된다

 

/*
            = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

이런 문제이다. 

1번에 있을때는 10보다 낮은게 3개니 -> 3
2번은 막혀서 -> 0
3번은 4층짜리를 볼 수 있어서 -> 1
4번도 막혀서 -> 0
5번은 1개 볼 수 있어서 -> 1
6번은 마지막이여서 -> 0

즉 계속 추가되는 수가 작으면 계속 값을 더해나가면 되는 것 같다.

1. 아파트 개수
2. 처음 기준이 되는 층
3. 10층을 넣었으면 10보다 같거나 작은 층은 지움.
4. 순회하면서 삭제하고 남은 1을 카운트.
5. 그리고 삭제된 요소를 다시 돌린다
*/
#include <iostream> 
#include <stack>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  stack<int> st;
  int n, hg;
  long result = 0;

  cin >> n;

  for(int i = 0; i < n; i++) {

    cin >> hg;

    if(st.empty()) {
      st.push(hg);
      continue;
    }
    
    while(!st.empty() && st.top() <= hg) {
      st.pop();
    }

    result += st.size(); 
    st.push(hg);
  }

  cout << result;
  return 0;
}

 이렇게 해설이 되겠다.