1027(고층 건물) - 해결

고층 건물

 

문제

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

 

입력

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

 

출력

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

---

N이 50이 최대이기 때문에 브루트포스로 풀면 되겠다고 생각을 하였다.

그 방법은 한 건물에서 볼 수 있는 건물을 확인하는 방법이다.

그러면 최대 50*49인데 줄일 수 있는 방법이 떠올랐다.

두 건물이 볼 수 있다면 같이 볼 수 있는 건물의 수를 증가시키면 되기 때문에 앞의 건물은 볼 필요가 없다는 것을 알았다.

그리고 사이의 건물을 보는 거라서 생각해보니깐 바로 옆에 있는 건물은 무조건 볼 수 있다.

그렇기 때문에 처음 볼 수 있는 건물은 양쪽 건물은 1 사이의 건물은 2이다.

그리고 건물은 선택할때는 다다음 건물부터 선택해서 사이의 확인하는 방식을 사용하였다.

핵심인 볼 수 있는지 확인하는 방법은 두 점을 지나는 선분을 구하는 식과 해당 점이 위에 있는지와 아래에 있는지 판단은 해당 식에 대입했을 때 0보다 크면 위 0이면 선에 0보다 작으면 아래에 있는 공식을 사용하였다.

import sys
input = sys.stdin.readline

N = int(input())

buildings = list(map(int,input().split()))

# 건물이 2개 이상일 때
if N != 1:
    # 건물이 2개 이상일 때 양끝의 건물은 바로 옆에 1개의 건물은 무조건 볼 수 있고
    # 가운데 건물의 경우 양쪽의 건물을 볼 수 있기 때문에 
    # 초기화를 1 2 ... 2 1 로 해준다. 
    ans_list = [1] + [2] * (N-2) + [1]

    # 앞 건물하나를 선택하고
    # 뒤의 건물을 하나씩 선택하며 사이의 건물이 가리는지 확인
    for i in range(N-2):
        for j in range(i+2,N):
            # 앞 건물과 뒤의 건물 옥상사이의 선을 연결
            # 두 점을 지나는 선분 구하는 식 ((x2-x1)*y + (y1-y2)*x + x1*y2 - x2*y1)
            line = [j-i,buildings[i]-buildings[j],i*buildings[j] - j*buildings[i]]

            # 사이의 건물을 보면서 
            # 옥상의 위치를 대입했을 때 0보다 크면 선 위에 있는거고 작으면 선 아래에 있는 것이다.
            for k in range(i+1,j):
                # 가운데의 건물 중 하나라도 선 위에 있다면 다음 건물 보기
                if line[0]*buildings[k] + line[1]*k + line[2] >= 0:
                    break
            # 만약 사이의 건물이 가리는게 없다면 
            # 서로 건물이 볼 수 있기 때문에 둘다 증가
            else:
                ans_list[i] += 1
                ans_list[j] += 1

    # 그 중 가장 큰 값 
    print(max(ans_list))
# 건물이 1개 이면 0 출력
else:
    print(0)