[백준/Python] 1027번. 고층 건물

문제

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

 

 

사고 과정

처음에는 서로 보이는지 판단할 두 빌딩 사이의 모든 빌딩이 두 빌딩의 높이보다  낮은 경우를 구하면 되지 않을까 싶었다.

하지만 이 그림과 같이 1, 3 두 빌딩 사이의 빌딩 2번은 3번보다 높은데도 불구하고 1과 3 빌딩은 서로를 볼 수 있어서 정답이 아니었다.

두번째로 사이의 빌딩들의 제한높이를 두 빌딩 의 높이의 차이를 이용해 수동으로 구하는 방법을 생각했는데

1과 4 사이의 높이 차이는 6이며 사이의 빌딩은 2개이므로 아래와 같이

높이의 차이를 2개로 쪼개 3등분한 값을 더해가며 제한 높이를 수동으로 구하여 풀어보았는데
이론상 정답인것 같으나 부동소숫점 연산의 부정확성 문제 추측되는 이유로 틀렸다.

 

 

풀이

따라서 아래와 같이 두 빌딩의 지붕 사이의 직선의 방정식을 구한 뒤

y = ax + b

a는 기울기(slope)로서 (y의 증가량 / x의 증가량)으로 구할 수 있다.

b는 y절편(yIntercept)으로서 직선을 지나는 특정 점의 위치에 대입하여 구할 수 있다. (이 문제에서는 두 빌딩중 아무 빌딩의 지붕의 좌표를 대입하여 구한다.)

두 빌딩 사이에 존재하는 빌딩들의 x값을 직선의 방정식에 대입하여 제한 높이 y(maxSeeHeight)를 구하고

제한 높이를 넘기는 빌딩이 존재하면 두 빌딩은 서로를 보지 못하므로 넘기고, 제한 높이를 넘기는 빌딩이 존재하지 않는다면 서로를 볼 수 있다는 말이므로 두 빌딩 서로의 set의 상대방을 볼 수 있다고 저장한다음

제일 긴 set의 길이를 출력하여 문제를 해결하였다.

 

 

 

 

정답 코드

from collections import defaultdict

N = int(input())
buildings = list(map(int, input().split()))
seeCount = defaultdict(set)

for idx in range(N):
    targetIdx = idx+1
    while targetIdx < N:
        isCanSeeTarget = True
        betweenIdx = idx + 1
        slope = (buildings[targetIdx] - buildings[idx]) / (targetIdx - idx)
        yIntercept = buildings[idx] - slope * idx  # y = slope * x + yIntercept 에 대입하여 정리한 식
        while betweenIdx < targetIdx:
            maxSeeHeight = slope * betweenIdx + yIntercept
            if buildings[betweenIdx] >= maxSeeHeight:
                isCanSeeTarget = False
                break
            betweenIdx = betweenIdx+1
        if isCanSeeTarget:
            seeCount[idx].add(targetIdx)
            seeCount[targetIdx].add(idx)
        targetIdx = targetIdx+1

answer = 0
for seeSet in seeCount.values():
    if answer < len(seeSet):
        answer = len(seeSet)

print(answer)