백준 6918 옥상 정원 꾸미기 c++

[문제 링크]

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

[입출력 예]

입력	출력
6 10 3 7 4 12 2	5

[1차 시도]

#include <bits/stdc++.h>
#define MAX_N 80000
#define MAX_h 1000000001
#define X first
#define Y second
int a[MAX_N];

using namespace std;

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

    // n값 입력
    int n;
    cin>>n;

    // 배열 입력
    for(int i=0; i<n;i++ ){
        cin>>a[i];
    }

    // <인덱스,높이>를 담는 스택
    stack <pair<int,int>> s;
    pair<int,int> p ={n,MAX_h};
    s.push(p);
    // 순회
    for (int i=n-1;i>=0; i--){
       while(s.top().Y<a[i]){
           s.pop();
       }
       ans+=s.top().X-i-1;
       s.push({i,a[i]});
    }
    cout<<ans;
    return 0;
}

[소스코드]

#include <bits/stdc++.h>
#define MAX_N 80000
#define MAX_h 1000000001
#define ll long long
#define X first
#define Y second
int a[MAX_N];

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll ans=0;

    // n값 입력
    ll n;
    cin>>n;

    // 배열 입력
    for(int i=0; i<n;i++ ){
        cin>>a[i];
    }

    // <인덱스,높이>를 담는 스택
    stack <pair<ll,int>> s;
    pair<ll,int> p ={n,MAX_h};
    s.push(p);
    // 순회
    for (int i=n-1;i>=0; i--){
       while(s.top().Y<a[i]){
           s.pop();
       }
       ans+=s.top().X-i-1;
       s.push({i,a[i]});
    }
    cout<<ans;
    return 0;
}

• 빌딩 갯수가 8만이고 N제곱이 64억이므로 ans를 long long으로 선언해주어야 한다.

[소스코드2]

// Authored by : unluckyjung
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/a84f083cdee3436f9f46acdef175e55f

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

#define ll long long

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

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

  cin >> n;
  ll h;
  while (n--) {
    cin >> h;
    while(!s.empty() && s.top() <= h)
      s.pop();

    // ans에는 현재 건물을 볼 수 있는 건물들의 수 만큼 더해진다.
    // 한 건물에서 몇 건물을 볼 수 있는지 세는 것이 아니라
    // 이 건물이 몇 건물에게 보여지는 지 세는 방식.
    // 스택에는 내림차순으로 건물이 정리된다.
    ans += s.size();
    s.push(h);
  }
  cout << ans;
  return 0;
}