백준 1027번 고층 건물 (c++)

중학교 1학년 때 배우는 함수를 이용하면 된다.

볼 수 있는 최소 건물의 높이를 구하는 함수는 f(x) = ax + b 가 된다.

처음에는 모든 건물을 볼 수 있으므로 a = - 999999999 모든 건물을 볼 수 있는 최소값을 잡고, b는 현재 건물의 높이가 들어가되면 된다. 

각 건물들을의 왼쪽과 오른쪽을 확인하면서 볼 수 있는 건물의 최소 높이 보다 높다면 num ++ 를 하고, 기울기 a 값을 업데이트 한다. 

각 건물별로 볼 수 있는 건물들을 확인하고 최대값을 출력하면 된다.

#include <iostream>

using namespace std;

int main()
{
    double building[50];
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> building[i];
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int num = 0;
        double ra = -9999999999;
        //right side
        for (int j = i + 1; j < n; j++)
        {
            double minH = building[i] + ra * (j - i);
            if (building[j] > minH)
            {
                num++;
                ra = (building[j] - building[i]) / (j - i);
            }
        }
        ra = -9999999999;
        //left side
        for (int j = i - 1; j >= 0; j--)
        {
            double minH = building[i] + ra * (i - j);
            if (building[j] > minH)
            {
                num++;
                ra = (building[j] - building[i]) / (i - j);
            }
        }
        ans = max(ans, num);
    }
    cout << ans << endl;
    return 0;
}