[BOJ] 1027 - 고층 건물

[백준] 1027 - 고층 건물

접근

가장 무식한 방법을 생각해보자. 각 건물에서 해당 건물이 보이는지 알아보기 위해 모든 건물에 대해 완전탐색을 실시해 내가 보려는 건물과 이어진 선분에 걸리는 건물이 있는지 확인하면 된다. 따라서 N x N x N=N³의 시간복잡도를 가질 것이다. 지금 다시 보니 이렇게 풀어도.. 풀릴 것 같은데.. 아무튼 조금만 더 생각해보면 현재 위치에서 각 건물까지 이은 선분의 기울기는 항상 증가(오른쪽으로 바라보는 경우)하거나 감소(왼쪽 방향으로 바라보는 경우)하게 될 것이다. 그래서 나는 현재 위치를 기준으로 두 번 봐주었는데 이 글을 쓰면서 생각해보니 왼쪽->오른쪽으로 봐준다면 기울기는 항상 증가하므로 기울기가 증가하는 경우를 세주기만 하면 된다(한번 보는데 N만큼의 시간이 걸린다) 따라서 O(N²)의 시간으로 계산할 수 있다.

소스코드

#include<iostream>
#include<limits.h>
#include<algorithm>
using namespace std;
typedef long long ll;

ll arr[55];

int main(void) {
	ll n, ans = 0;
	scanf("%lld", &n);
	for (ll i = 0; i < n; i++) {
		scanf("%lld", arr + i);
	}
	for (ll i = 0; i < n; i++) {
		ll cnt = 0;
		if (i > 0) {
			ll x = i - 1;
			cnt++;
			for (ll j = i - 2; j >= 0; j--) {
				if ((j - i) * (arr[x] - arr[i]) > (x - i) * (arr[j] - arr[i])) {
					x = j;
					cnt++;
				}
			}
		}
		if (i < n - 1) {
			ll x = i + 1;
			cnt++;
			for (int j = i + 2; j < n; j++) {
				if ((j - i) * (arr[x] - arr[i]) < (x - i)* (arr[j] - arr[i])) {
					x = j;
					cnt++;
				}
			}
		}
		ans = max(ans, cnt);
	}
	printf("%d", ans);
	return 0;
}