[백준 1027] 고층 건물

www.acmicpc.net/problem/1027

1027번: 고층 건물

N = int(input())
bd= list(map(int,input().split()))

def left_view(i):
    line = 10000000000
    view = 0
    cur_idx = i-1
    while cur_idx >= 0:
        dx = i-cur_idx
        dy = bd[i] - bd[cur_idx]
        dydx = dy/dx

        if dydx < line:
            view+=1
            line = dydx
        cur_idx-=1
    return view

def right_view(i):
    line = -10000000000
    view = 0
    cur_idx = i+1
    while cur_idx < N:
        dx = cur_idx-i
        dy = bd[cur_idx] - bd[i]
        dydx = dy/dx

        if dydx > line:
            view+=1
            line = dydx
        cur_idx+=1
    return view

idx = 0
max_view = 0
for i in range(N):
    l = left_view(i)
    r = right_view(i)
    # print("=======")
    # print("빌딩 인덱스 :",i)
    # print("빌딩 왼쪽 :",l)
    # print("빌딩 오른쪽 :",r)
    total = l+r
    if max_view < total:
        max_view = total
        idx = i

print(max_view)

풀이

처음엔 스택인가 했다. 이런류의 스택문제가 많기 때문에 그렇게 생각했다. 하지만 N이 작고 이중포문으로 체크하면 끝날 하나씩 다 체크해도 시간이 충분할 것 같았기 때문에 생각을 멈추고 아래와 같이 구현했다.

 

각각 빌딩에서 볼 수 있는 최대 빌딩의 수를 구한다.

빌딩 수가 50 이하이므로 이중포문을 돌려도 충분하다.

 

1. 빌딩에서 왼쪽을 볼때

- 빌딩 바로 왼쪽부터 왼쪽 끝까지 진행

- 기울기가 지속적으로 감소해야 한다.

- 최대로 작았던 기울기르 저장해놓고 그것보다 작은 기울기가 나왔을 때만 값을 추가한다.

 

2. 빌딩에서 오른쪽을 볼때

- 빌딩 바로 오른쪽부터 오른쪽 끝까지 진행

- 기울기가 지속적으로 증가해야 한다.

- 최대로 큰 기울기를 저장해놓고 그것보다 큰 기울기가 나왔을 때만 값을 추가한다.

 

시간복잡도

N개의 빌딩이 존재하고, 빌딩마다 전체 N개의 빌딩을 탐색하기 때문에 O(N^2) 이다.