백준 1027 / C++

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

1027번: 고층 건물

 

[ 풀이 ] 

 

1. 건물 s와 건물 e가 서로 보일 조건은 두 건물 사이의 건물들의 높이가 두 건물을 이은 직선보다 아래에 있으면 된다. 

직선 식을 세워서 보이는지 확인하는 check 함수를 만들어준다. O(N)에 처리할 수 있다.  

 

2. 모든 건물쌍에 대해 check 를 만족하면, cnt[s]와 cnt[e]를 갱신해준다. 

cnt[i]는 건물i에서 볼수있는 건물의 수이다. 

 

3. 시간복잡도는 각 쌍 N^2개에 대해 check함수 O(N)이므로 O(N^3)에 문제를 해결할 수 있다. 

 

 

[ 코드 ] 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll h[55];
int n, cnt[55];

int check(int s, int e) {
	for (int k = s + 1; k < e; k++) {
		if ((h[e] - h[s]) *(k - s) <= (e - s) * (h[k] - h[s])) return 0;
	}
	return 1;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> h[i];
	for (int s = 1; s < n; s++) {
		for (int e = s + 1; e <= n; e++) {
			if (check(s, e)) {
				cnt[s]++;
				cnt[e]++;
			}
		}
	}
	cout << *max_element(cnt, cnt + 55) << '\n';
}