1027. 고층 건물 골드IV

문제

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

문제는 이렇다. 일정 높이를 가지는 건물들 중에서 가장 건물이 많이 보이는 건물의 개수를 출력한다.

접하면 안된다 했으므로 걸쳐도 안된다.

 

기울기를 이용하면 풀 수 있는 문제다. 현재 위치에서 기울기를 구해 그 기울기보다 작으면 개수를 추가하고 그렇지 않으면 다음으로 넘어가면 된다.

 

헤맸던 이유는 크기 때문이었다. 빌딩마다 처음 각도를 -99999999999로 설정 해줘야 했는데 작은 값으로 해서 틀렸다.

왜 틀렸나 곰곰히 생각해보니 입력의 크기가 최대 10억이었다. 그것만 알면 쉬웠다.

 

 

#include <cstdio>
 
int main()
{
    int n, MAP[50],ans=0,score[50]={0,};
    scanf("%d", &n);
    for(int i=0;i<n;i++)
        scanf("%d", &MAP[i]);
    for(int i=0;i<n;i++)
    {
        long double angle = 1.0*-99999999999;
        for(int j=i+1; j<n; j++)
        {
            long double now = 1.0*(MAP[j]-MAP[i])/(j-i);
            if(now > angle){
                angle = now;
                score[i]++;
                score[j]++;
            }
        }
    }
 
    for(int i=0;i<n;i++)
        if(score[i]>ans)
            ans = score[i];
    printf("%d\n", ans);
 
    return 0;
}