수학, 브루트포스 - 1027번: 고층 건물

• 현재 idx 기준 왼쪽에 위치한 빌딩의 경우: m2 <= m 일 때 빌딩 i는 가려짐
• 현재 idx 기준 오른쪽에 위치한 빌딩의 경우: m2 >= m 일 때 빌딩 i는 가려짐

n = int(input())
heights = list(map(int, input().split()))


max_cnt = 0

# 각 idx에서 보이는 빌딩 수 중 최대값 구하기
for idx in range(0, n):
    cnt = 0 # 현재 idx에서 보이는 빌딩 수

    # i: 현재 idx의 왼쪽에 위치한 빌딩 i가 보이는지 확인하기
    for i in range(0, idx):
        # m: idx빌딩과 i빌딩의 기울기
        m = (heights[idx] - heights[i]) / (idx - i)
        cant_see = False

        # j: 빌딩 i와 idx 사이에 위치한 모든 빌딩을 확인
        for j in range(i + 1, idx):
            # m2: idx빌딩과 j빌딩의 기울기
            m2 = (heights[idx] - heights[j]) / (idx - j)
            
            # m2가 m보다 작거나 같다면 i빌딩은 idx에서 보이지 않음
            if m2 <= m: 
                cant_see = True
                break
        # 사이의 모든 빌딩이 시야를 가리지 않았다면 i빌딩을 idx에서 볼 수 있음
        if not cant_see:
            cnt += 1    
    
    
    # i: 현재 idx의 오른쪽에 위치한 빌딩 i가 보이는지 확인하기
    for i in range(idx + 1, n): # (idx + 1 ~ n - 1)
        m = (heights[idx] - heights[i]) / (idx - i)
        cant_see = False

        for j in range(idx + 1, i):
            # i와 idx사이에 모든 건물에 대해서 확인
            m2 = (heights[idx] - heights[j]) / (idx - j)
            
            if m2 >= m: # idx의 오른쪽에 위치한 빌딩이므로 부호 반전해야 함 주의
                cant_see = True
                break

        if not cant_see:
            cnt += 1    

    # 현재 idx에서 볼 수 있는 cnt가 max_cnt보다 크다면 갱신
    max_cnt = max(max_cnt, cnt)

print(max_cnt)