고층 건물 C++ - 백준 1027

https://acmicpc.net/problem/1027

문제 접근

이 문제는 완전탐색이고, 겹치는 경우가 없게 탐색해야 한다.

$i$번째 건물과 $j$번째 건물이 서로를 볼 수 있으려면,

$(i,H_i)$ 와 $(j,H_j)$ 를 이은 일차함수가

그 사이 건물들에 대해 항상 높아야 한다.

이를 구현한 코드는 다음과 같다.

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

int n;
int arr[51];
int d[51];
int ans=0;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    memset(d,0,sizeof(d));
    for(int i=1;i<=n;i++) cin >> arr[i];
    for(int a=1;a<n;a++){
        d[a]++; d[a+1]++;
        for(int b=a+2;b<=n;b++){
            double til=(double)(arr[b]-arr[a])/(b-a);
            double c=-til*a+arr[a];
            bool t=true;
            for(int i=a+1;i<b;i++){
                if(til*i+c<=arr[i]){t=false;break;}
            }
            if(t){d[a]++;d[b]++;}
        }
    }
    for(int i=1;i<=n;i++) ans=max(ans,d[i]);
    cout << ans;
}