[백준 1027번] 고층 건물 문제 풀이

 

< 문제 >

 

 

< 입출력 >

 

 

 

< 풀이 >

이 문제를 풀기 위해서는 i 번째 건물에서 (N-1)개의 건물들과 기울기를 구해서 비교해야 한다.

 

이때, i 번째 빌딩을 기준으로 왼쪽에 있는 경우, 가까운 건물들의 기울기 보다 작으면 보이고,

i 번째 빌딩을 기준으로 오른쪽에 있는 경우, 가까운 건물들보다 기울키가 크면 보인다.

 

따라서, 가까운 빌딩들부터 순서대로 기울기를 구하고, 왼쪽의 경우 더 작은 기울기가 있으면 +1, 오른쪽의 경우 더 큰 기울기가 있으면 +1 해준다.

 

 

< 코드 >

N = int(input())
building = list(map(int, input().split()))
INF = int(1e10)
def angle(i, h1, j, h2):
    return (h2-h1)/(j-i)

count = [0] * N    # 각 i 빌딩에서 보이는 빌딩들의 개수


for i in range(N):
    standard_left = [INF] * N          # 왼쪽 빌딩 기준 
    standard_right = [-INF] * N        # 오른쪽 빌딩 기준 
    for j in range(i-1, -1, -1):
        left_angle = angle(i, building[i], j, building[j])

        if min(standard_left) > left_angle:  # 기준 빌딩 보다 작으면 count+1
            standard_left[j] = left_angle
            count[i] += 1

        else:
            standard_left[j] = min(standard_left)
    for j in range(i+1, N):

        right_angle = angle(i, building[i], j, building[j])

        if max(standard_right) < right_angle:   # 기준 빌딩 보다 크면 count +1
            standard_right[j] = right_angle
            count[i] += 1
        else:
            standard_right[j] = max(standard_right)

print(max(count))