BOJ 6198 옥상 정원 꾸미기

문제

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

Bad Hair Day 문제로, 자신의 오른쪽에서 자기보다 큰 키의 소가 나오기 전까지 소들의 수를 세주는 문제이다.

 

 

풀이

$O(N^2)$ 풀이로는, 각 소를 기준으로 자신보다 높은 소가 나올때까지 카운팅해서 풀 수도 있다.

 

이럴 땐 한번 관점을 바꾸어 생각해 보자.

나의 입장에서 보이는 소들의 수를 세는 것이 아니라, 내가 보여지는 소들의 수를 셀 수는 없을까?

내가 보여지는 소들은

1. 나보다 뒤에 있으며

2. 나와 그 소 사이의 모든 소는 나보다 작아야 한다.

 

이것을 어떻게 이용할 수 있을까?

한번 손으로 직접 그 수열에서 각 소가 보여지는 소들의 리스트를 만들어 보면, 내림차순이 됨을 알 수 있다.

이제 이것을 이용하여 이미 계산된 것들을 이용하는 스위핑 알고리즘을 설계하자.

 

스택을 이용하여 자기보다 큰 원소들밖에 없을 때까지 뺀다.

그렇다면 남아 있는 값들은 모두 자신을 볼 수 있는 소들이므로, 답에 추가한다.

그 이후에 자신도 스택에 추가한다.

 

이 과정을 반복하면 답을 구할 수 있고, 모든 소들은 스택에 한번씩 들어갔다가 한번 나오기 때문에, 시간복잡도는 $O(N)$ 이다.

 

시간 복잡도 : $O(N)$

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 80000;

int n, arr[MAXN+10];
ll ans;

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    scanf("%d", &n);
    for(i=1; i<=n; i++) scanf("%d", &arr[i]);

    vector<int> S;
    for(i=1; i<=n; i++)
    {
        while(!S.empty() && S.back()<=arr[i]) S.pop_back();
        ans+=S.size();
        S.push_back(arr[i]);
    }

    printf("%lld", ans);
    return 0;
}