백준(BOJ) 1027 고층 건물(Python)

문제 내용

간단한 브루트포스 문제이다.

n의 크기가 그리 크지 않기 때문에 따로 시간복잡도 계산을 하지 않고도 브루트포스 문제임을 쉽게 알 수 있었다.

현재 서있는 빌딩에서 보고 싶은 빌딩을 고르고, 그 빌딩과의 선분을 연결한 뒤 기울기와 y절편을 이용해 두 빌딩 사이에 있는 빌딩 중 선분보다 높은 빌딩이 없다면 ans에 1을 더하고, 그렇지 않으면 continue하는 방식으로 알고리즘을 구현했다.

​

코드는 다음과 같다.

n=int(input())
L=list(map(int,input().split()))
ans=0
for i in range(n):
    c=0
    for j in range(n):
        if i==j:
            continue
        a=(L[j]-L[i])/(j-i)
        b=L[j]-a*j
        if i<j:
            flag=0
            for k in range(i+1,j):
                if L[k]>=a*k+b:
                    flag=1
                    break
            if not flag:
                c+=1
        else:
            flag=0
            for k in range(j+1,i):
                if L[k]>=a*k+b:
                    flag=1
                    break
            if not flag:
                c+=1
    ans=max(ans,c)
print(ans)

알고리즘 분류를 꺼야하나 싶다.

문제에 어떤 알고리즘을 사용해야할 지 파악하는 것도 능력이라고 생각하는데, 그렇지 않으니 문제를 푸는 재미가 반감되는 것 같기도 하다.

시간복잡도 계산을 잘 못해서 그 부분을 연습하는 것도 중요할 것 같다.