[백준/1027] 고층 건물 (Python)

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

1027번: 고층 건물

 

Difficulty : Gold 4

 

Status : Solved

 

Time : 00:11:46

 

---

 

문제 설명

 

 

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

 

입력 및 출력

 

입력

 

첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

 

출력

 

첫째 줄에 문제의 정답을 출력한다.

 

입력 예시

 

15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5

 

출력 예시

 

7

 

 

---

 

풀이

 

어떤 건물에서 오른쪽 방향으로 서로 보이는 건물들의 선분을 그려보자. 그 선분들은 부채꼴 형태를 띄게 될 것이다. 즉, 어떤 건물이 보이는지 여부를 판단하려면, 기존의 가장 큰 기울기의 선분보다 더 큰 기울기를 가져야만 한다. 이렇게 오른쪽으로 탐색하며 모든 건물들간의 기울기를 계산하면, O(N^2) 시간복잡도 내에 최대 빌딩 수를 구할 수 있다.

 

풀이 코드

N = int(input())
building_list = list(map(int, input().split()))
answer = [0]*N

for i in range(N-1) :
  max_slope = -float('inf')
  for j in range(i+1, N) :
    slope = (building_list[j] - building_list[i]) / (j - i)
    if slope <= max_slope :
      continue
    max_slope = max(max_slope, slope)
    answer[i] += 1
    answer[j] += 1

print(max(answer))

풀이 완료!