[BOJ] 1027. 고층 건물

문제

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

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

 

---

 

주요 아이디어

• 단순 길이비교 문제가 아님에 유의할 것
• 직선의 경사를 통해 풀이하는 문제
• target의 오른쪽에 위치한 빌딩들의 경우, 이전 건물들보다 기울기가 크면 됨

출처 : https://nerogarret.tistory.com/57

• target의 왼쪽에 위치한 빌딩들의 경우, 이전 건물들보다 기울기가 작으면 됨

출처 : https://nerogarret.tistory.com/57

 

---

 

코드 구현 (Python 3)

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

n = int(input())
heights = list(map(int, input().split()))
max_building_cnt = 0

for i1, h in enumerate(heights):
    cnt = 0
    previous = None
    # 왼쪽 빌딩들 확인
    for i2 in range(i1-1, -1, -1):
        if i2 == -1: break
        if previous == None or slope(i1, h, i2, heights[i2]) < previous:
            previous = slope(i1, h, i2, heights[i2])
            cnt += 1
    
    previous = None
    # 오른쪽 빌딩들 확인
    for i3 in range(i1+1, n):
        if i3 == n: break
        if previous == None or slope(i1, h, i3, heights[i3]) > previous:
            previous = slope(i1, h, i3, heights[i3])
            cnt += 1
    
    max_building_cnt = max(cnt, max_building_cnt)
            
print(max_building_cnt)

 

---

 

 

제출 결과