[BOJ] #1027 고층 건물(Bruteforce, Python)

🌱 문제

1027번: 고층 건물

 

🌱 풀이

1. 기울기 계산

def calc_gradient(x1, y1, x2, y2):
    if x1 == x2:
        return 0
    gradient = (y2 - y1) / (x2 - x1)
    return gradient

건물이 보이는지 여부는 기울기에 따라 결정되므로 기울기를 계산하는 함수를 작성합니다.

 

1. 완전탐색 (Bruteforce)

results = []
for idx in range(len(buildings)):
    cnt = 0

    min_gradient = INF
    for i in range(idx - 1, -1, -1):
        gradient = calc_gradient(i, buildings[i], idx, buildings[idx])
        if gradient < min_gradient:
            cnt += 1
            min_gradient = gradient

    max_gradient = -INF
    for i in range(idx + 1, len(buildings)):
        gradient = calc_gradient(i, buildings[i], idx, buildings[idx])
        if gradient > max_gradient:
            cnt += 1
            max_gradient = gradient

    results.append(cnt)

• 완전탐색으로 모든 건물들의 기울기를 비교하여 보이는 건물의 개수(cnt)를 카운트합니다.
• 왼쪽 건물들은 현재까지 측정한 최소 기울기(min_gradient)보다 기울기가 크면 보이지 않습니다.
• 오른쪽 건물들은 현재까지 측정한 최대 기울기(max_gradient)보다 기울기가 작으면 보이지 않습니다.

 

🌱 코드

# !usr/bin/env python
# -*- coding: utf-8 -*-
# boj 1027 고층건물

import sys
INF = sys.maxsize

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

def calc_gradient(x1, y1, x2, y2):
    if x1 == x2:
        return 0
    gradient = (y2 - y1) / (x2 - x1)
    return gradient

results = []
for idx in range(len(buildings)):
    cnt = 0

    min_gradient = INF
    for i in range(idx - 1, -1, -1):
        gradient = calc_gradient(i, buildings[i], idx, buildings[idx])
        if gradient < min_gradient:
            cnt += 1
            min_gradient = gradient

    max_gradient = -INF
    for i in range(idx + 1, len(buildings)):
        gradient = calc_gradient(i, buildings[i], idx, buildings[idx])
        if gradient > max_gradient:
            cnt += 1
            max_gradient = gradient

    results.append(cnt)

print(max(results))