[BOJ/백준][Gold4] 1027 : 고층 건물 (C++)

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

1027번: 고층 건물

 

[난이도] Gold4
[유형] 수학

[풀이]
어떤 건물 i에서 j를 볼 수 있으려면 i+1~j-1 인 어떤 모든 k에 대해
i,j의 기울기가 i,k의 기울기보다 커야한다.
i,j를 볼 수 있다는 것은 j에서도 i를 볼 수 있다는 것이다.
2중 for문으로 모든 i,j 짝에 대해 볼 수 있는지 확인할 수 있다.

 

#include <cstdio>
int N,a[50],ans,c[50];
double getD(int i,int j){
    return (a[j]-a[i])/(double)(j-i);
}
int main(){ 
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    for(int i=0;i<N-1;i++){
        double cur,d;
        for(int j=i+1;j<N;j++){
            d = getD(i,j);
            if(j-1==i || cur < d){
                cur = d;
                c[i]++; c[j]++;
            }
        }
    }
    for(int i=0;i<N;i++) if(ans < c[i]) ans=c[i];
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1027.cpp