문제

• 
• 시간 제한: 2초
• 메모리 제한: 128MB

Problem Analysis

각 빌딩에서 볼 수 있는 빌딩의 수를 구해 그 중에서 최대를 찾는 방법 외에는 특별한 방법이 없다. 기울기를 이용하여 문제를 풀면 되는데, double은 부정확하기 때문에, 분모 분자를 나누어 비교해 주면 된다.

Algorithm

각 빌딩에서 가까운 곳에 있는 빌딩부터 점차 먼 곳 비교하면 된다. 이때, 각 파트에서 현재까지 조사한 기울기보다 더 큰 기울기를 갖는 빌딩의 개수만 세어주면 된다. 또한, 왼쪽에서 볼 수 있는 빌딩의 수와 오른쪽에서 볼 수 있는 빌딩의 수 두 가지를 따로 구해야 한다.

Data Structure

• int buildings[]: 각 빌딩의 높이를 저장

결과

Other

시간 복잡도는 O(N^2)이다.