[BOJ] 1027

고층 건물

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

분류

• Gold 4

• 수학
• 기하학

해법

i번째 건물과 j번째(i < j) 번째 건물이 서로 볼 수 있는 건물이라고 할 때,
i번째 건물과 j + 1번째 건물이 서로 볼 수 있는 건물이려면
i번째 건물과 j번째 건물의 옥상을 잇는 선분보다 i번째 건물과 j + 1번째 건물의 옥상을 잇는 선분의 기울기가 더 커야합니다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int N;
int b[55];
int cnt[55];

void sol() {
    for (int i = 1; i <= N; i++) {
        double mx_incl = -0x7f7f7f7f;
        for (int j = i + 1; j <= N; j++) {
            double incl = (b[j] - b[i]) / (double)(j - i);
            if (incl > mx_incl) {
                mx_incl = incl;
                cnt[i]++;
                cnt[j]++;
            }
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> b[i];
    }
    sol();
    cout << *max_element(cnt, cnt + 55);
    return 0;
}