백준 1027 고층 건물 Python

🐸 문제 정보

1027번: 고층 건물

 

🤖 알고리즘

수학

 

⏱️ 풀이 시간

15.12m

 

📝 풀이

단순한 스택 문제라고 생각했는데, 기울기를 비교해야하는 수학 문제였다.

오히려 스택보다 조건 자체는 쉽다.

 

오른쪽으로 이동하면서 이전까지 나왔던 최대 기울기보다 큰 기울기가 나와야만 1개를 추가해준다.

A와 B 빌딩 서로 볼 수 있기 때문에 두 요소 모두 1을 추가해야한다.

이런식으로 모든 요소를 탐색하면 되는 문제였다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
nums = list(map(int, input().rstrip().split()))
res = [0] * n

for i in range(n - 1):
    temp = -sys.maxsize
    for j in range(i + 1, n):
        if temp < (nums[j] - nums[i]) / (j - i):
            res[i] += 1
            res[j] += 1
            temp = (nums[j] - nums[i]) / (j - i)

print(max(res))