[BOJ] 백준 1027번: 고층 건물

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

1027번: 고층 건물

 

기울기를 이용한 문제입니다. ccw 알고리즘을 이용하여 세점의 방향성으로도 풀 수 있습니다. 여기 참고<< 

귀찮으니 기울기값을 이용하여 풀어봤습니다.

i번째 건물을 기준으로 왼쪽의 건물을 보려면 j번째 건물이 i번째 건물에서 보이려면 i-1~j+1 구간의 기울기의 최소값보다 j번째건물의 기울기 값이 더 작아야 볼 수 있습니다.

반대로, i번째 건물 기준으로 오른쪽 건물들은 기울기의 최대값보다 커야 i번째 건물에서 볼 수 있습니다.

소수점 오차를 줄이기 위해 식을 수정하여 비교했습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	ll n, a[51], ans =0;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		ll left = i - 1;
		ll right = i + 1;
		ll cnt = 0;
		for (int j = i-1; j >-1; j--) {
			if (j == i - 1) {
				cnt += 1;
				continue;
			}
			ll d1 = (i - j);
			ll h1 = (a[i] - a[j]);
			ll d2 = (i - left);
			ll h2 = (a[i] - a[left]);
			// h1/d1 < h2/d2 여야 보임
			if (h1 * d2 < h2 * d1) {
				left = j;
				cnt += 1;
			}
		}
		for (int j = i + 1; j < n; j++) {
			if (j == i + 1) {
				cnt += 1;
				continue;
			}
			ll d1 = (i - j);
			ll h1 = (a[i] - a[j]);
			ll d2 = (i - right);
			ll h2 = (a[i] - a[right]);
			// h1/d1 > h2/d2 여야 보임
			if (h1 * d2 > h2 * d1) {
				right = j;
				cnt += 1;
			}
		}
		ans = max(cnt, ans);
	}
	cout << ans;
}