백준 1027 : 고층 건물

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

1027번: 고층 건물

 

해결 방법 : 브루트포스

• 각 건물에서 모든 경우를 탐색
• 건물 X에 대해, X에서 왼쪽으로 탐색을 진행한다면 (건물 X와 왼쪽의 건물X' )의 꼭대기를 잇는 직선의 기울기가 이전의 기울기 보다 작아질 때, 건물 X'를 볼 수 있음을 알 수 있다. 
  • 오른쪽 건물 X''의 경우 기울기가 커질 때 해당 건물을 볼 수 있다.
• 따라서 임의의 건물 X를 기준으로 left, right로 각각 모든 건물을 탐색하며 left 방향은 기울기가 작아지는 갱신 count, right 방향은 기울기가 커지는 갱신 count를 합한 것이 X에서 볼 수 있는 건물을 수가 된다.

import sys
input = sys.stdin.readline

def solution(N, heights):
    counts = [0] * N # 해당 건물에서 볼 수 있는 다른 건물 수
    weight = lambda x1,y1,x2,y2 : (y2 - y1) / (x2 - x1) # 기울기 구하기

    for x in range(N): # 브루트포스
        l_w, r_w = float('inf'), -float('inf') # left는 min 방향 탐색, right는 max 방향 탐색이므로

        for l_x in range(x - 1, -1, -1): # 왼쪽 건물들 탐색
            n_w = weight(x, heights[x], l_x, heights[l_x]) # 기울기
            if n_w < l_w: # 더 작아지면 갱신 및 count ++
                l_w = n_w
                counts[x] += 1

        for r_x in range(x + 1, N):
            n_w = weight(x, heights[x], r_x, heights[r_x])
            if n_w > r_w: # 더 커지면 갱신 및 count ++
                r_w = n_w
                counts[x] += 1

    return max(counts)

if __name__ == '__main__':
    N = int(input())
    heights = list(map(int, input().split()))
    result = solution(N, heights)
    print(result)