[BOJ 6198] 옥상 정원 꾸미기 (C++)

www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

옥상 정원 꾸미기 문제

구현 방법

이 문제는 스택을 활용해야 하는 문제입니다.

 

1. 첫 번째 건물은 바로 스택에 넣어줍니다.

2. 두 번째 건물 입력부터 다음 로직을 거쳐 줍니다

   i) 스택에 있는 건물들 중에, 현재 건물보다 작은 건물들을 다 빼줍니다.

   ii) 건물을 다 빼줬으면, 스택에 있는 개수만큼 답에 더해줍니다.

   iii) 해당 입력을 스택에 넣어줍니다.

 

※ 주의 할 점 ※

이 문제의 로직 자체는 간단했습니다.

 

하지만 저는 기초적인것을 생각하지 않아 계속 답안이 틀렸습니다.

 

이 문제의 입력을 보면 빌딩의 개수 N개가 (1 <= N <= 80,000)입니다.

 

예를들어 첫번째 빌딩의 높이가 80001, 두번째가 80000, .... N번째가 1이면 볼수 있는 건물의 개수는

80000 + 79999+ 79998 + .... + 1 입니다.

 

이를 식으로 나타내면 1부터 N까지의 합으로 n(n+1)/2로 n^2입니다.

 

입력의 최대값인 80000^2는 6,400,000,000이므로 int형이 나타낼 수 있는 범위를 초과합니다.

 

즉 answer 변수를 int 형으로 선언하면 안되고 long long형으로 선언해야 합니다.

 

구현 방법 설명

백준에 있는 예를 들어 설명하겠습니다.

 

입력된 건물들의 높이는 10, 3, 7, 4, 12, 2입니다.

각각 건물"을" 볼 수 있는 건물의 수는 다음과 같습니다.

건물 번호	1	2	3	4	5	6
건물 높이	10	3	7	4	12	2
보는 건물 갯수	0개	1개 (1번)	1개 (1번)	2개 (1,3번)	0개	1개 (5번)

이 내용을 그림으로 표현하면 다음과 같습니다.

1. 첫 번째 입력인 10은 그냥 스택에 넣어줍니다.  stack = [10]

 

2. 그다음 입력은 3입니다.

   i) 스택에 있는 건물 중에, 현재 입력보다 높은 건물이 나올 때까지 빼줍니다.

      지금 상황에선 stack = [10]이니 3보다 작은 건물이 없어서 빼줄 게 없습니다.

   ii) 스택의 개수만큼 정답에 더해줍니다.   answer = 1

   iii) 스택에 새로운 건물을 넣어줍니다.  stack = [10, 3]

 

   => 이 과정으로 높이가 3인 건물을 볼 수 있는 건물인 7, 즉 1개가 정답에 추가되었습니다.

 

3. 그다음 입력은 7입니다

   i) 스택에 있는 건물 중에, 현재 입력보다 높은 건물이 나올 때까지 빼줍니다.

      지금 상황에선 stack = [10, 3]이니 7보다 작은 3만 빼줍니다. stack = [10]

   ii) 스택의 개수만큼 정답에 더해줍니다.   answer = 1 + 1

   iii) 스택에 새로운 건물을 넣어줍니다.    stack = [10, 7]

 

   => 이 과정으로 높이가 7인 건물을 볼 수 있는 건물인 10, 즉 1개가 정답에 추가되었습니다.

 

4. 그다음 입력은 4입니다.

   i) 스택에 있는 건물 중에, 현재 입력보다 높은 건물이 나올 때까지 빼줍니다.

      지금 상황에선 stack = [10, 7]이니 4보다 작은 건물이 없어서 빼줄 게 없습니다.

   ii) 스택의 개수만큼 정답에 더해줍니다.   answer = 1 + 1 + 2

   iii) 스택에 새로운 건물을 넣어줍니다.   stack = [10, 7, 4]

 

   => 이 과정으로 높이가 4인 건물을 볼 수 있는 건물인 10, 7 즉 2개가 정답에 추가되었습니다.

 

5. 그다음 입력은 12입니다.

   i) 스택에 있는 건물 중에, 현재 입력보다 높은 건물이 나올 때까지 빼줍니다.

      지금 상황에선 stack = [10, 7, 4]이니 전부 12보다 작아 전부 빼줍니다.

   ii) 스택의 개수만큼 정답에 더해줍니다.   answer = 1 + 1 + 2 + 0

   iii) 스택에 새로운 건물을 넣어줍니다.   stack = [12]

 

   => 이 과정으로 높이가 12인 건물을 볼 수 있는 건물이 없으므로 0개가 정답에 추가되었습니다.

 

6. 그다음 입력은 2입니다.

   i) 스택에 있는 건물 중에, 현재 입력보다 높은 건물이 나올 때까지 빼줍니다.

      지금 상황에선 stack = [12]이니 2보다 작은 건물이 없어서 빼줄 게 없습니다.

   ii) 스택의 개수만큼 정답에 더해줍니다.   answer = 1 + 1 + 2 + 0 + 1

   iii) 스택에 새로운 건물을 넣어줍니다.   stack = [12, 2]

 

   => 이 과정으로 높이가 2인 건물을 볼 수 있는 건물인 12 즉 1개가 정답에 추가되었습니다.

 

이 일련의 과정을 입력의 개수만큼 반복하면 됩니다.

 

위 로직은 다음과 같이 구현했습니다.

 

소스 코드

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int count;
    stack<int> s;
    long long answer = 0;
    cin >> count;

    for(int i=0;i<count;i++) {
        //새로운 높이 입력 받음
        int height;
        cin >> height;

        //1. 첫번째 건물은 바로 스택에 넣어줌
        if(s.empty()) {s.push(height); continue;}

        //2. i) 스택에 있는 건물들 중에, 현재 건물 보다 작은 건물들은 다 빼줍니다.
        while(!s.empty() && s.top() <= height)
            s.pop();

        //2. ii) 건물을 다 빼줬으면, 스택에 있는 개수만큼 답에 더해줍니다.
        answer += s.size();

        //2. iii) 해당 입력을 스택에 넣어줍니다.
        s.push(height);
    }

    cout << answer;
}