(Python/파이썬) - 백준(BOJ) 1027번 : 고층 건물

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

1027번: 고층 건물

---

• 문제 : 

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

 

 

 

---

• 풀이 :

수학 문제였습니다. 

문제의 핵심은 다른 건물이 보이는 조건을 찾는 것입니다.

 

예를 들어, 1 2 7 3 2의 높이를 가진 5개의 건물이 있을 때 3번째 건물의 관점에서 본다면

(왼쪽)

7 -> 2를 바라본 기울기는 (7 - 2)/(3 - 2) = 5 입니다. 

7 -> 1을 바라본 기울기는 (7 - 1)/(3 - 1) = 3 입니다.

 

(오른쪽)

7 -> 3을 바라본 기울기는 (7 - 3)/(3 - 4) = -4 입니다.

7 -> 2를 바라본 기울기는 (7 - 2)/(3 - 5) = -2.5 입니다.

 

3번 건물에서 좌, 우의 모든 건물을 관측할 수 있으므로 답은 4 입니다.

 

위의 예시로 알 수 있는 관측 가능한 조건은 다음과 같습니다.

 

탐색 중인 건물의 왼쪽 -> 현재까지 탐색한 건물 사이의 기울기 최솟값보다 기울기가 더 작아지는 건물일 경우

탐색 중인 건물의 오른쪽 -> 현재까지 탐색한 건물 사이의 기울기 최댓값보다 기울기가 더 커지는 건물일 경우

(음수일 경우도 적용됩니다.)

 

 

 

풀이입니다.

 

1. 모든 건물에 대해 탐색을 실시한다.

 

2. 각 빌딩에서 좌, 우로 몇 개의 건물을 볼 수 있는지 카운트한다.

 

3.  기울기를 계산하기 위해 calc 함수를 생성하고 탐색 중인 건물을 기준으로 좌, 우의 모든 건물을 탐색하며 관측 가능한 건물의 개수를 카운트한다.

 

4. 매 건물마다 관층 가능한 카운트하여 최댓값으로 갱신한다.

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

def calc(x1,y1,x2,y2):
    return (y2-y1)/(x2-x1)

N = int(input())
building = list(map(int,input().split()))
answer = 0
for idx, b in enumerate(building):
    view_max = 0
    left_max = float('inf') # 왼쪽의 기울기 최솟값
    right_max = -float("inf") # 오른쪽 기울기 최댓값
    for i in range(idx-1,-1,-1):  # 왼쪽
        c = calc(idx+1,b,i+1,building[i]) 
        if c < left_max: # 기울기가 더 작다면
            left_max = c 
            view_max += 1
    for i in range(idx+1,N):  # 오른쪽
        c = calc(idx+1,b,i+1,building[i])
        if c > right_max: # 기울기가 더 크다면
            right_max = c
            view_max += 1
    answer = max(answer,view_max)
print(answer)