문제
https://www.acmicpc.net/problem/1027
문제해설
높이가 다른 건물들의 높이 n개가 주어진다.
옥상에서 다른 건물들이 가장 많이 보이는 빌딩의 번호를 출력하면 된다.
문제풀이
이 문제는 기울기를 이용해 풀었다.
2중 반복문을 돌며 현재 건물 기준으로
다른 건물들의 기울기를 전부 계산해준다.
기울기가 계산해둔 최대값보다 크다면 볼 수 있는 것으로 판단했다.
그리고 최대값을 갱신해준다.
결과를 배열에 저장해두고 가장 큰 인덱스를 출력해주었다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
vector<int>arr(n + 1);
vector<int>cnt(n + 1, 0);
for (int i = 1; i <= n; i++)
cin >> arr[i];
for (int now = 1; now <= n; now++) {
double maxx = -9999999999;
for (int i = now + 1; i <= n; i++) {
double level = (double)(arr[i] - arr[now]) / (i - now);
if (level > maxx) {
cnt[now]++;
cnt[i]++;
maxx = level;
}
}
}
int res = 0;
for (int i = 1; i <= n; i++)
res = max(res, cnt[i]);
cout << res;
return 0;
}