[백준/BOJ] #1027 고층건물.python(파이썬)

문제 링크 / 출처

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

1027번: 고층 건물

 

풀이

numpy모듈을 사용하려했으나 백준에서는 RuntimeError가 발생하여 다른 방법을 사용했다.

 

기준 건물(A), 가까운 건물(B), 먼 건물(C)라고 할 때, A-B사이의 기울기의 값이 A-C사이의 기울기보다 클 경우,

 

A에서 C가 보이지 않으므로 이 점을 활용하여 문제풀이 하였다.

 

한쪽에서 보이는 건물은 다른쪽에서도 보인다. A에서 B가 보인다면, B에서도 A가 보인다는 의미이다.

 

따라서, 기준건물에서 우측건물들만 확인하면서, 기준건물을 우측으로 한칸씩 옮기며 확인한다.

 

기울기의 최댓값일 경우 그 뒤의 건물들은 보이지 않으므로 탐색중에 기울기의 최대값이 나오면,

 

최대값을 갱신하고 카운트을 하나씩 늘렸다.

 

두 건물 사이의 기울기의 최솟값이 -1,000,000,000이므로, 이 값보다 작은 값을 사용하여 MG를 초기화 하였다.

 

코드

# 기준 건물과 가까운 건물간의 기울기보다 작은 경우 안보임
# 한쪽에서 보이면 다른쪽도 보임

N = int(input())
BH = [int(b) for b in input().split()]  # BH : building_height
table = [[0 for _ in range(N)] for _ in range(N)]

for BB in range(N - 1):                 # BB : base_building
    MG = -1000000001                    # MG : max_gradient

    for CB in range(BB + 1, N):         # CB : compare_building
        gradient = (BH[CB] - BH[BB]) / (CB - BB)

        if gradient > MG:
            MG = gradient
            table[BB][CB] = table[CB][BB] = 1    # 한쪽에서 보이면 다른쪽에서도 보이므로 양쪽에 모두 추가

building_lst = []
for i in range(N):
    building_lst.append(sum(table[i]))  # 각 건물에서 보이는 건물 수 계산

print(max(building_lst))