[BOJ] 백준 1027번 고층 빌딩 문제 풀이 (Python)

1. 문제 풀이 방법

문제에서 '고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다.'라는 조건이 있었기 때문에 두 건물의 지붕을 잇는 선분의 기울기를 이용하여 문제를 풀었다.

1. 각 건물들 사이의 기울기를 모두 구한다.
2. 각 건물에 대해서 볼 수 있는 건물들의 갯수를 구한다.
   • A와 B 사이의 건물을 K라고 지칭할 때
   • B가 A의 왼쪽에 있는 경우
     • K와 A의 기울기가 B와 A의 기울기보다 같거나 작으면 볼 수 없다.
   • B가 A의 오른쪽에 있는 경우
     • K와 A의 기울기가 B와 A의 기울기보다 같거나 크면 볼 수 없다.
3. 가장 많은 건물이 보이는 건물을 구하고 거기서 보이는 건물의 수를 출력한다.

특정 알고리즘을 사용할 필요 없이 문제 조건과 작성한 풀이에 맞춰 구현하였다.

2. 코드

import sys
def input(): return sys.stdin.readline().rstrip()

n = int(input())
buildings = list(map(int,input().split()))
grad = [[0] * n for _ in range(n)]

# 각 건물 사이의 기울기 구하기
# grad[i][j]: i 건물과 j 건물 사이의 기울기
for i in range(n):
    for j in range(n):
        if i == j: continue
        grad[i][j] = (buildings[i] - buildings[j]) / (i-j)

# 각 건물에서 볼 수 있는 건물의 갯수 구하기
# max_cnt[A]: A 건물에서 볼 수 있는 건물의 갯수
max_cnt = [0] * n
for i in range(n):
    cnt = 0
    # 왼쪽에서 볼 수 있는 건물 갯수 구하기
    for l in range(i):
        possible = True
        for k in range(l+1,i):
            if grad[k][i] <= grad[l][i]:
                possible = False
        if possible: cnt += 1
    # 오른쪽에서 볼 수 있는 건물 갯수 구하기
    for r in range(i+1,n):
        possible = True
        for k in range(i+1,r):
            if grad[i][k] >= grad[i][r]:
                possible = False
        if possible: cnt += 1
    max_cnt[i] = cnt
print(max(max_cnt))