[Gold IV] 고층 건물 - 1027

문제 링크

성능 요약

메모리: 32412 KB, 시간: 48 ms

분류

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

문제 설명

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

입력

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

출력

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

---

문제 풀이

문제 분석

이 문제는 N개의 건물이 주어졌을 때, 각 건물에서 다른 건물을 볼 수 있는 건물의 수를 계산하고, 그 중 가장 많은 건물을 볼 수 있는 건물이 몇 개의 건물을 볼 수 있는지 출력하는 문제입니다. 두 건물을 잇는 선분이 다른 건물을 지나거나 접하지 않아야 볼 수 있다고 정의합니다. 입력은 건물의 수 N과 각 건물의 높이입니다. 출력은 가장 많은 건물을 볼 수 있는 건물이 보이는 건물의 수입니다.

접근 방법

이 문제는 모든 건물에 대해 다른 모든 건물을 볼 수 있는지 확인하는 완전 탐색(브루트 포스) 방식으로 해결할 수 있습니다. 두 건물 i와 j를 잇는 선분이 다른 건물 k를 지나거나 접하는지 확인하는 것은 기하학적인 계산을 통해 판단할 수 있습니다. N의 최대값이 50이므로 완전 탐색으로도 시간 제한 내에 해결 가능합니다.

구현 설명

1. 입력 받기

• 건물의 수 N과 각 건물의 높이 h를 입력 받습니다. input() 함수와 map() 함수를 사용하여 입력을 처리합니다.

2. check(i, j) 함수 정의

• check(i, j) 함수는 건물 i에서 건물 j를 볼 수 있는지 여부를 판단합니다. 건물 i와 j 사이에 있는 모든 건물 k에 대해, 건물 k가 건물 i와 j를 잇는 선분 위에 있거나 선분을 가로지르는지 확인합니다.

• 건물 i와 j를 잇는 직선의 방정식을 구하고, 건물 k의 x좌표에서의 y좌표 값을 계산합니다. 이 y좌표 값이 건물 k의 높이보다 크거나 같으면, 건물 k가 건물 i와 j를 잇는 선분 위에 있거나 선분을 가로지르는 것입니다.

• check(i, j) 함수는 건물 i에서 건물 j를 볼 수 있으면 True를, 그렇지 않으면 False를 반환합니다.

3. 최대 보이는 건물 수 계산

• 각 건물 i에 대해, 다른 모든 건물 j를 순회하며 건물 i에서 건물 j를 볼 수 있는지 check(i, j) 함수를 통해 확인합니다.

• 건물 i에서 볼 수 있는 건물의 수를 세고, 이 값이 현재까지 찾은 최대 보이는 건물 수보다 크면 최대 보이는 건물 수를 갱신합니다.

4. 결과 출력

• 최대 보이는 건물 수를 출력합니다.

⏱복잡도 분석

• 시간 복잡도: check 함수는 O(N)의 시간이 걸립니다 (두 건물 사이에 있는 모든 건물에 대해 검사). 이 함수를 모든 건물 쌍 (N * N)에 대해 호출하므로 총 시간 복잡도는 O(N^3)입니다.
• 공간 복잡도: 건물의 높이를 저장하는 리스트 h는 O(N)의 공간을 사용합니다. 그 외 변수들은 상수 공간을 사용하므로 총 공간 복잡도는 O(N)입니다.

핵심 포인트

1. 기하학적 판단: 두 건물을 잇는 선분이 다른 건물을 가리는지 판단하는 정확한 조건을 이해하는 것이 중요합니다. 기울기를 비교하거나, 특정 x좌표에서 선분의 y좌표 값과 건물의 높이를 비교하는 방법을 사용해야 합니다.
2. 완전 탐색의 적절성: 문제의 제약 조건(N <= 50)을 통해 완전 탐색이 시간 내에 완료될 수 있음을 파악하는 것이 중요합니다.
3. 코드 가독성: check 함수를 사용하여 코드를 모듈화하고 가독성을 높이는 것이 좋습니다.

풀이 코드

import sys

input = sys.stdin.readline

n = int(input())
h = list(map(int, input().split()))

def check(i, j):
    if i < j:
        for k in range(i+1, j):
            if h[k] * (j - i) >= h[i] * (j - i) + (h[j] - h[i]) * (k - i):
                return False
    else:
        for k in range(i-1, j, -1):
            if h[k] * (i - j) >= h[i] * (i - j) + (h[j] - h[i]) * (i - k):
                return False
    return True

max_cnt = 0
for i in range(n):
    cnt = 0
    for j in range(n):
        if i != j and check(i, j):
            cnt += 1
    max_cnt = max(max_cnt, cnt)

print(max_cnt)