BOJ 1027, 고층 건물
ProblemSolving ·이 문제는 수학 문제입니다.
풀이
이 문제는 한 건물에서 다른 건물을 볼 수 있는 숫자 중에서 가장 큰 수를 구하는 문제이다.
다른 건물을 볼 수 있는지의 판단은 각 건물의 옥상에서 선분을 그었을 때 겹치지 않는 않는 숫자이다.
그것은 선분의 기울기로 비교할 수 있다.
예를 들어 첫 번째 건물이 3이고 두 번째 건물이 4라면 (다음 건물이 더 큰 경우)
다음에 볼 수 있는 건물은 두 번째 건물보다 크고 첫 번째 건물과의 선분의 기울기가 더 커야 볼 수 있다.
만약 첫 번째 건물이 3이고 두 번째 건물이 2라면 (다음 건물이 더 작은 경우)
다음에 볼 수 있는 건물은 두 번째 건물보다 크고 첫 번째 건물과의 선분의 기울기가 더 커야 볼 수 있다.
결국은 어떤 경우던지 처음 건물을 볼 때의 기울기보다 점점 더 큰 값의 기울기가 나와야 건물을 더 볼 수 있다.
#include<iostream>
#include<algorithm>
using namespace std;
double n, h[51],ans[51];
int main() {
scanf("%lf", &n);
for (int i = 0; i < n; i++)
scanf("%lf", &h[i]);
for (int i = 0; i < n-1; i++)
{
double Max = -1e9;
for (int j = i + 1; j < n; j++)
{
double compare = (h[j] - h[i]) / (j - i);
if (compare > Max)
Max = compare,ans[i]++,ans[j]++;
}
}
sort(ans, ans + (int)n);
printf("%d", (int)ans[(int)n - 1]);
return 0;
}