BOJ 1027 고층 건물

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

문제

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

---

입력

첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

---

출력

첫째 줄에 문제의 정답을 출력한다.

---

예제 입력 1

15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5

예제 출력 1

7

예제 입력 2

1
10

예제 출력 2

0

… 이하 예제 생략

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int[] buildings;
    static double[][] angles;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        buildings = new int[N];
        angles = new double[N][N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            buildings[i] = Integer.parseInt(st.nextToken());
        }

        // 각각의 빌딩 사이의 기울기를 계산
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(i == j) continue;

                double distance = i - j;
                angles[i][j] = (buildings[i] - buildings[j]) / distance;
            }
        }

        int answer = 0;
        for (int i = 0; i < N; i++) {
            answer = Integer.max(answer, search(i));
        }

        System.out.println(answer);
    }

    static int search(int idx) {
        int count = 0;

        /**
         * 검사 대상 빌딩의 왼쪽에 존재하는 빌딩들 검사
         * 왼쪽에 있는 빌딩을 대상으로 한 검사이기 때문에, 기울기가 작으면 작을 수록 높은 건물임
         */
        double minAngle = Double.MAX_VALUE;
        for (int i = idx - 1; i >= 0; i--) {
            if(minAngle > angles[idx][i]) {
                count++;
                minAngle = angles[idx][i];
            }
        }

        /**
         * 검사 대상 빌딩의 오른쪽에 존재하는 빌딩들 검사
         * 오른쪽에 있는 빌딩을 대상으로 한 검사이기 때문에, 기울기가 크면 클 수록 높은 건물임
         */
        double maxAngle = -Double.MAX_VALUE;
        for (int i = idx + 1; i < N; i++) {
            if(maxAngle < angles[idx][i]) {
                count++;
                maxAngle = angles[idx][i];
            }
        }

        return count;
    }
}