[BOJ][🟡4][백준#01027] 고층 건물

문제 출처

BAEKJOON Online Judge #1027

문제

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

입력

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

출력

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

예제

예제 1

입력

15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5

출력

7

예제 2

입력

1
10

출력

0

예제 3

입력

4
5 5 5 5

출력

2

예제 4

입력

5
1 2 7 3 2

출력

4

예제 5

입력

10
1000000000 999999999 999999998 999999997 999999996 1 2 3 4 5

출력

6

My Sol

def main(std_i):
    ret = 0
    for k in range(1, std_i):
        ret += check(std_i, k)

    for k in range(std_i+1, N+1):
        ret += check(std_i, k)

    return ret

def check(std_i, k):
    dx = std_i - k
    dy = arr[std_i] - arr[k]
    s = dy/dx
    [b, e] = [k+1, std_i] if std_i > k else [std_i+1, k]

    for j in range(b, e):
        std_h = s*j + (arr[k] - s*k)
        if arr[j] >= std_h:
            return 0
    return 1


N = int(input())
arr = [0] + list(map(int, input().split()))
ret = 0
for std_i in range(1, N+1):
    ret = max(ret, main(std_i))

print(ret)

모든 빌딩들에 대하여 각 빌딩을 기준점으로 좌우의 모든 빌딩들에 대해 옥상을 잇는 직선의 식을 구하고, 그 사이에 이 직선을 통과하거나 접하는 직선이 없다면 빌딩을 볼 수 있는 것이므로 매 건물을 기준점으로 잡을 때마다 최고점을 갱신하였다. 이후 최고점을 출력해주었다.

결과

맞았습니다!!

모범답안

출처

from sys import stdin

n = int(stdin.readline())
h = list(map(int, stdin.readline().split()))

able_to_see = [0] * n

for i in range(n):
    inc = -1000000000
    for j in range(i+1, n):
        slope = (h[j] - h[i]) / (j - i)
        if slope > inc:
            inc = slope
            able_to_see[i] +=1
            able_to_see[j] +=1
    
print(max(able_to_see))

연산시간도 조금 짧고 길이가 획기적으로 짧은 풀이가 있어 가져왔다. 각 빌딩 지점을 기준점으로 하였는데, 최초 -inf로 둔 inc가 slope보다 작으면 slope로 inc를 갱신하고 배열의 i와 j를 1씩 추가해주었다. 이런 발상을 어떻게 했는가 싶다.