[Baekjoon] 1027번: 고층 건물 (완전탐색 - 브루트포스 Gold4) - Python

1. 문제

고층 건물

2. 코드

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

N = int(input())
heights = list(map(int, input().split()))
maxViewCount = 0

for i in range(N):
    viewCount = 0
    
    maxSlopeRight = -float('inf') // 음의 무한대로 초기화
    for j in range(i+1, N):
        slopeRight = slope(i, heights[i], j, heights[j])
        if maxSlopeRight < slopeRight:
            maxSlopeRight = slopeRight
            viewCount += 1

    minSlopeLeft = float('inf') // 양의 무한대로 초기화
    for j in range(i-1, -1, -1):
        slopeLeft = slope(i, heights[i], j, heights[j])
        if slopeLeft < minSlopeLeft :
            minSlopeLeft = slopeLeft
            viewCount += 1

    maxViewCount = max(maxViewCount, viewCount)

3. 로직

1. 첫 번째 빌딩부터 마지막 빌딩까지 순회하면서 해당 빌딩에 위치했을 때 보이는 빌딩의 수를 계산하기 위해 viewCount 변수를 0으로 초기화 시킨다.

2. 현재 위치한 빌딩을 기준으로 오른쪽부터 순차적으로 탐색한다.

• maxSlopeRight 변수에는 현재까지 발견한 오른쪽 방향으로의 기울기 중에서 가장 큰 값이 저장되어 있을 것이다.
• 기준 빌딩으로부터 오른쪽으로 차례대로 탐색하면서 새로운 빌딩을 발견할 때마다 기울기를 계산하여 slopeRight 변수에 저장한다.
• 이는 최대 기울기를 나타내는 maxSlopeRight 변수의 값보다 무조건 커야지 눈에 보이는 빌딩인 것으로 간주하므로, 해당 조건에 만족하면 viewCount를 증가시킨다.

3. 이후엔 현재 위치한 빌딩을 기준으로 왼쪽을 순차적으로 탐색한다.

• minSlopeLeft 변수에는 현재까지 발견한 왼쪽 방향으로의 기울기 중에서 가장 작은 값이 저장되어 있을 것이다.
• 기준 빌딩으로부터 왼쪽으로 차례대로 탐색하면서 새로운 빌딩을 발견할 때마다 기울기를 계산하여 slopeLeft 변수에 저장한다.
• 이는 최소 기울기를 나타내는 minSlopeLeft 변수의 값보다 무조건 작아야지 눈에 보이는 빌딩인 것으로 간주하므로, 해당 조건에 만족하면 viewCount를 증가시킨다.

4. 탐색을 마친 후엔 maxViewCount 값과 viewCount 값을 비교하여 더 큰 값을 maxViewCount에 저장한다. 이를 통해 가장 많은 고층 빌딩이 보이는 빌딩의 개수를 최종적으로 구한다.