BOJ 1027 - 고층 건물 링크
(2022.11.21 기준 G4)

문제

(i,0)부터 (i,높이)의 선분으로 나타낼 수 있는 빌딩 i가 N개가 있다.
다른 빌딩을 보려면 두 지붕을 잇는 선분이 다른 빌딩을 지나거나 접하면 안된다.
가장 많이 보이는 빌딩의 수 출력

알고리즘

모든 빌딩마다 볼 수 있는 빌딩의 수를 구해 최댓값을 출력하면 된다.

풀이

이런 빌딩들이 있고 세번째 빌딩에서 볼 수 있는 빌딩의 수를 구해보자.

일단 왼쪽으로 살펴보자.
당연히 바로 왼쪽 빌딩은 볼 수 있다.

하지만 첫번째 빌딩은 볼 수 없다. 선분을 이어보면 위로 볼록하다.

이제 오른쪽으로 살펴보자.
당연히 바로 오른쪽 빌딩은 볼 수 있다. 그리고 다섯번째 빌딩도 볼 수 있다. 선분을 이어보면 아래로 볼록하다.

여섯번째 빌딩도 볼 수 있다. 선분을 이어보면 아래로 볼록하다.

하지만 마지막 빌딩은 볼 수 없다. 선분을 이어보면 위로 볼록하다.

결국은 이런 것이다.
구하고자 하는 빌딩을 기준으로 왼쪽과 오른쪽을 살펴봐야 한다.
바로 양 옆은 볼 수 있다. 그 뒤로는 (기준이 되는 빌딩, 마지막으로 보인 빌딩, 보이는지 확인하는 빌딩)의 CCW 값을 구하자.
왼쪽이면 시계 방향이어야 하고, 오른쪽이면 반시계 방향이어야 한다.

이를 모든 빌딩마다 구해 최댓값을 출력하면 된다.

코드

import sys; input = sys.stdin.readline

def ccw(a, b, c):
    return (a[0] * b[1] + b[0] * c[1] + c[0] * a[1]) - (a[1] * b[0] + b[1] * c[0] + c[1] * a[0])

def solve():
    N = int(input())
    if N < 3: # 빌딩이 1개나 2개면 보이는 빌딩은 0개나 1개다.
        print(N - 1)
        return
    H = list(map(int, input().split()))

    answer = 0
    # 모든 빌딩마다 보이는 빌딩의 수를 구해야 한다.
    for i in range(N):
        result = []
        # 왼쪽
        if 0 < i: # 기준 빌딩의 index가 0보다 커야 한다.
            result.append(i - 1)
            for j in range(i - 2, -1, -1):
                if ccw([i, H[i]], [result[-1], H[result[-1]]], [j, H[j]]) < 0:
                    result.append(j)
        # 오른쪽
        if i < N - 1: # 기준 빌딩의 index가 N - 1보다 작아야 한다.
            result.append(i + 1)
            for j in range(i + 2, N):
                if ccw([i, H[i]], [result[-1], H[result[-1]]], [j, H[j]]) > 0:
                    result.append(j)
        answer = max(answer, len(result))
    print(answer)

solve()