백준 / 1027 / 고층 건물 / C++

문제 링크 : https://www.acmicpc.net/problem/1027

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    int n;
    cin >> n;
    vector<double> height(n);
    vector<int> count(n,0);
    for(int i = 0; i < n; i++)
    {
        cin >> height[i];
    }
    for(int i = 0; i < n - 1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(i + 1 == j)
            {
                count[i]++;
                count[j]++;
                continue;
            }
            bool flag = false;
            for(int k = i + 1; k < j; k++)
            {
                double stand = ((height[i] * (j - k)) + (height[j] * (k - i))) / (j - i);
                if(height[k] >= stand)
                {
                    flag = true;
                    break;
                }
            }
            if(!flag)
            {
                count[i]++;
                count[j]++;
            }
        }
    }
    cout << *max_element(count.begin(),count.end());
}

문제에서 요구하는 것에 대한 발상 자체는 어렵지 않다. 기준이 되는 빌딩과 나머지 빌딩들 각각을 잇는 선을 그은 후, 그 선을 넘어서는 빌딩이 있는지 체크한 후에 없다면 카운트를 증가시키고, 지나가는(가리는) 빌딩이 있다면 넘어가는 로직을 생각할 수 있다.

문제는 어떤 발상으로 이것을 구현하느냐인데, 나는

• 마지막 빌딩을 제외한 전체 각각의 빌딩에 대해서 (빌딩A)
• 그 빌딩의 오른쪽에 있는 빌딩들에 대해 (빌딩B)
• 만약 빌딩 B가바로 오른쪽에 있는(맞붙어있는)빌딩이라면 무조건 볼 수 있으므로 카운트 +1
• 그 외의 빌딩이라면 위 로직을 체크한 후 볼 수 있는 빌딩이라면 빌딩A와 빌딩B의 카운트를 증가

하는 방법을 사용했다. 이 방법을 사용한다면 최악의 경우 $O(N^3)$의 시간 복잡도를 가지게 되고, N이 50보다 작거나 같으므로 충분히 통과할 수 있을 것이라 생각했다.

이렇게 카운트를 계산한 후, 배열에서 최댓값을 뽑아 출력해주면 성공