[Gold IV] 고층 건물 - 1027

문제 링크

성능 요약

메모리: 31120 KB, 시간: 44 ms

분류

브루트포스 알고리즘, 기하학, 수학

제출 일자

2023년 10월 11일 20:04:00

문제 설명

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

입력

첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

풀이

아이디어

맨 처음에는 선분간의 교차판정을 통해 하려고 ccw 알고리즘에 대해 알아봤는데 굳이 그럴 필요 없을 것 같아 기울기 판정으로만 문제를 풀이하였다.
get_tilt()함수를 통해 기울기를 구하고, n개의 빌딩을 모두 탐색하면서 개수를 세어 나가는 방식으로 문제를 풀이하였다.

이때 기준 빌딩을 중심으로 오른쪽과 왼쪽 탐색이 기울기 조건이 다르므로 2중 for문 아래에서 비슷하지만 다른 조건을 찾아 각각처리해준 뒤, 배열에 넣어 해결하였다.

코드

n = int(input())
buildings = list(map(int, input().split()))
result = [0]*(n)
if n == 1:
    print(0)
    exit()

def get_tilt(cidx, nidx):
    x1, x2 = cidx, nidx
    y1, y2 = buildings[cidx], buildings[nidx]
    return (y1 - y2) / (x1 - x2)

for i in range(n):
    tilt = float('INF')
    res = 0
    for j in range(i-1, -1, -1):
        if (tmp:=get_tilt(i, j)) < tilt:
            tilt = tmp
            res += 1

    tilt = -float('INF')  
    for k in range(i+1, n):
        if (tmp:=get_tilt(k, i)) > tilt:
            tilt = tmp
            res += 1
    result[i] = res

print(max(result))

---

회고

구현이 약간 헷갈리긴 햇지만 G4문제 치고는 풀만했다.