[백준 알고리즘: python 3] #1027 - 고층 건물

https://www.acmicpc.net/problem/1027

 

1027번 문제는 겉보기에 그렇게 어렵지 않게 보이지만, 약간의 수학적인 아이디어가 필요한 문제입니다. 여기서 사용된 수학적인 아이디어란, 어떤 건물에서 다른 건물을 볼 수 있는 조건이 수학적으로 어떻게 해석되느냐? 에 대한 답을 할 수 있어야 한다는 것이었네요.

 

Hint!

문제에서는 어떤 건물(x1, y1)에서 다른 건물(x2, y2)을 볼 수 있으려면, 두 건물을 이은 선분이 다른 건물을 지나거나 접하지 않아야 한다고 했습니다. 아래의 그림은 임의의 한 건물을 기준으로 오른쪽을 볼 때, 볼 수 있는 건물들이 무엇이 있는지 보여준 것입니다. 아이디어 설명을 위해 그렸네요.

 

볼 수 있는 건물은 O 표시를 그렇지 않은 것은 X 표시를 했습니다. (아이패드 편하다...)

 

우선, 빨간색 건물을 기준으로 본다고 할 때, 저는 이 건물의 오른쪽에서 가장 가까운 건물을 순서대로 이 건물을 볼 수 있는 것인지 살펴볼 것입니다. 즉, X축에 표시된 1, 2, 3번 건물을 순서대로 탐색을 할건데, 이 때 두 건물의 지붕을 잇는 선분의 기울기에 집중하려고 합니다. 먼저, 빨간색 건물과 1번 건물을 보면 두 지붕을 잇는 선분의 기울기는 1입니다. 가장 가까운 건물이니까 이 건물은 당연히 볼 수 있는 건물이 되겠죠? 다음, 2번 건물과의 지붕 사이 기울기는 2.5입니다. 즉, 2번 건물은 볼 수 있습니다. 그 이유는 2번 건물의 지붕과 잇는 선분의 기울기가 앞에 있는 1번 건물과 잇는 선분의 기울기보다 크기 때문에 빨간 건물에서 2번 건물을 보기 위한 각도가 나오기 때문입니다. 하지만, 3번 건물은 볼 수 없습니다. 그 이유는 단순히 2번 건물보다 높이가 낮기 때문이 아니고 애초에 빨간 건물에서 3번 건물의 지붕과 잇는 선분의 기울기가 앞의 2번 건물과의 기울기보다 작기 때문에 볼 수 있는 각도가 안나오기 때문입니다.

 

이런 식으로 건물의 오른쪽에서 볼 수 있는 건물을 세려면, 가까운 건물부터 기울기를 계산했을 때 앞에서 나온 최대의 기울기보다 크면 볼 수 있는 건물의 수에 1을 더해주면 됩니다. 무조건 기울기가 커지기만 하면 될까요? 네. 됩니다. 아래 그림은 빨간 건물이 위의 그림과 달리 높은 건물일 때 나올 수 있는 상황입니다.

 

이 그림에서 알 수 있듯이, 기울기가 음수가 되든 양수가 되든(건물을 아래서 내려다 보든 위로 올려다 보든) 다음 건물과 잇는 선분의 기울기가 앞선 건물의 기울기보다 크면 볼 수 있는 건물이 되는 것입니다. 4번 건물 이후의 건물을 볼 수 있으려면 앞서 나온 기울기 중 최댓값인 0.33333 이상의 기울기를 가질 수 있는 건물이 등장해주면 되겠네요.

 

빨간 건물의 왼쪽에서 볼 수 있는 건물을 세려면 어떻게 해야 할까요? 왼쪽에서 볼 수 있는 건물은 오른쪽에서 볼 수 있는 건물의 조건과 반대로 앞서 나온 기울기의 최소보다 기울기가 작아지면 볼 수가 있습니다. 이 부분은 위에서 설명한 오른쪽에서 볼 수 있는 건물들과 설명이 비슷하기 때문에 아래의 그림만 첨부해드리고 넘어갈게요! 스스로 생각해 보시기에 충분합니다. 4번 건물의 -0.25의 기울기는 3번 건물에서 -0.3333이라는 더 작은 기울기가 나왔기 때문에 볼 수 없는 건물이 되어요.

 

주어지는 건물의 수는 최대 50개이기 때문에, 모든 건물에 대해서 왼쪽과 오른쪽 건물들 중 볼 수 있는 건물들 중 최댓값을 계속 업데이트 하면서 순회해 주면 답을 구할 수 있습니다.

 

아래의 코드로 성공하였습니다. 주석된 print문을 풀면, 코드가 어떻게 돌아가는지 알 수 있으니 코드를 먼저 보고 이해하고 싶으시다면 주석을 출고 한 번 살펴봐 주세요.

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

N = int(input())

buildings = list(map(int, input().split()))

result = 0
for i1, y1 in enumerate(buildings):
    x1 = i1 + 1
    # 오른쪽 볼 수 있는 빌딩 수
    cur_slope_right = None
    visible_right = 0
    for i2 in range(i1+1, N+1):
        if i2 == N: break
        x2 = i2 + 1
        y2 = buildings[i2]
        slope_right = slope(x1, y1, x2, y2)
        # print("RIGHT:", x1, y1, x2, y2, slope_right)
        if cur_slope_right is None or cur_slope_right < slope_right:
            cur_slope_right = slope_right
            visible_right += 1
    # print("visible_right:", visible_right)

    # 왼쪽 볼 수 있는 빌딩 수
    cur_slope_left = None
    visible_left = 0
    for i3 in range(i1-1, -1, -1):
        if i3 == -1: break
        x2 = i3 + 1
        y2 = buildings[i3]
        slope_left = slope(x1, y1, x2, y2)
        # print("LEFT:", x1, y1, x2, y2, slope_left)
        if cur_slope_left is None or cur_slope_left > slope_left:
            cur_slope_left = slope_left
            visible_left += 1
    # print("visible_left:", visible_left)

    if (visible_left + visible_right) > result: result = visible_left + visible_right

print(result)