[백준/Python] 10271번(완탐)_고층 건물

📌문제 유형

수학, 브루트포스 알고리즘, 기하학(골드 Lv.4)

 

📌문제

1027번: 고층 건물

 

📌나의 문제풀이

- i는 현재 확인하려는 고층건물, j는 i의 조건에 적합한지 확인하는 고층건물.

- k는 i,j 선분에 고층건물이 있는지 확인

• 방정식으로 선분 만들고, y값 비교 

n = int(input())
y = list(map(int,input().split()))
x = [i for i in range(1,n+1)]
coord = list(zip(x,y))

result = []
ans = 0

for i in range(len(coord)):
    for j in range(len(coord)):
        flag = 0
        if i == j:
            continue
        else:
            x1, y1 = coord[i]
            x2, y2 = coord[j]

        for k in range(min(i,j)+1, max(i,j)):
            tmp = ((y2-y1) / (x2-x1)) * (coord[k][0]-x1) + y1
            if coord[k][1] >= tmp:
                flag = 1
                break

        if flag == 0:
            ans += 1
        
    result.append(ans)
    ans = 0
print(max(result))

 

📌 다른사람의 문제풀이

- 기울기 각도에 따른 비교

- 왼쪽은 이전 값보다 작은 경우 += 1, 오른쪽은 이전 값보다 큰 경우 += 1

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

 

[백준 알고리즘: python 3] #1027 - 고층 건물

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)

 

📌 리뷰

- 수학적으로 접근하는 과정도 필요하다!