[BOJ 1027] 고층 건물

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

 

메인 알고리즘은 아래와 같다.

for(int i=1; i<=n; i++) {  // 각 건물마다
    int cnt = 0;
    
    // 왼쪽 건물들 체크 → cnt 증가
    // 오른쪽 건물들 체크 → cnt 증가
    
    res = max(res, cnt);  // 최댓값 갱신
}

 

단 왼쪽, 오른쪽 건물들을 확인할 때 사이 건물들과의 기울기도 계속해서 비교를 해준다.

#include <iostream>
#include <algorithm>
using namespace std;

int n, res;
int arr[51];

int main() {
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> arr[i];
    }

    for(int i=1; i<=n; i++) {
        int cnt = 0;
        
        // 왼쪽 확인
        for(int j=1; j<i; j++) {
            bool visible = true;
            double gradient_a = (arr[i] - arr[j]) / double(i - j);

            for(int k=j+1; k<i; k++) {
                double gradient_b = (arr[i] - arr[k]) / (double)(i-k);
                if (gradient_a >= gradient_b) {
                    visible = false;
                    break;
                }
            }
            if(visible) cnt++;
        }
        
        // 오른쪽 확인
        for(int j=i+1; j<=n; j++) {
            bool visible = true;

            double gradient_a = (arr[j] - arr[i]) / double(j-i);
            for(int k=i+1; k<j; k++) {
                double gradient_b = (arr[k] - arr[i]) / (double)(k-i);
                if(gradient_a <= gradient_b) {
                    visible = false;
                    break;
                }
            }
            if(visible) cnt++;
        }
        
        res = max(res, cnt);
    }

    cout << res << "\n";
    return 0;
}