백준 - 1027번 : 고층 건물 (C++)

풀이 방법 : 브루트 포스

두 빌딩 사이의 직선의 방정식을 세워 해당 식에 두 빌딩 사이의 빌딩들의 좌표들을 각각 대입했을 때 사이에 있는 빌딩중 하나라도 해당 직선보다 높은 녀석이 있을 경우 그 빌딩은 볼 수 없는 빌딩이다.

y = ax + c
a = (y1 - y2) / (x1 - x2)
c = y - ax

[다른 좌표 끼리만 비교할 것이므로 (x1 - x2)가 0일 일은 없다.]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int N;
	cin >> N;

	vector<int> vecBuilding(N + 1);
	vector<int> vecLookable(N + 1);

	for (int i = 1; i < N + 1; ++i)
	{
		cin >> vecBuilding[i];
	}

	for (int i = 1; i < N; ++i)
	{
		int MaxIdx = i + 1;

		for (int j = i + 1; j < N + 1; ++j)
		{
			double Cond = (vecBuilding[j] - vecBuilding[i]) / (double)(j - i);
			double Constant = vecBuilding[i] - Cond * i;

			bool Enable = true;

			for (int k = i + 1; k < j; ++k)
			{
				if (Cond * k + Constant <= vecBuilding[k])
				{
					Enable = false;
					break;
				}
			}

			if (Enable)
			{
				++vecLookable[i];
			}			
		}
	}

	for (int i = N; i > 1; --i)
	{
		int MaxIdx = i - 1;

		for (int j = i - 1; j > 0 ; --j)
		{
			double Cond = (vecBuilding[j] - vecBuilding[i]) / (double)(j - i);
			double Constant = vecBuilding[i] - Cond * i;

			bool Enable = true;

			for (int k = i - 1; k > j; --k)
			{
				if (Cond * k + Constant <= vecBuilding[k])
				{
					Enable = false;
					break;
				}
			}

			if (Enable)
			{
				++vecLookable[i];
			}
		}
	}

	int Answer = *max_element(vecLookable.begin(), vecLookable.end());

	cout << Answer;
}