[Gold IV][JAVA]백준 1027번:고층 건물

문제 바로가기>[Gold IV]백준 1027번:고층 건물

태그

• 수학
• 브루트포스 알고리즘
• 기하학

풀이과정

• 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하라.
• 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 

지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. A와 B를 이은 선분의 기울기를 따져보면 쉽게 문제를 해결할 수 있다.

건물 A와 건물 B를 이은 선분의 기울기  = 건물 A의 높이 - 건물 B의 높이 / 건물 A와 B의 거리

가장 높은 고층 빌딩(max)이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하라. 임의의 건물에서 왼쪽과 오른쪽을 탐색을 해야한다.

오른쪽 = 기울기 감소 , 왼쪽 = 기울기 증가

ex. 오른쪽 탐색 (기울기가 증가해야함)
13번째 건물과 14번째 건물 기울기 비교
= -4.0 vs -3.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[] arr;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        arr = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        int result = 0;
        for (int i = 1; i <= N; i++) {
            result = Math.max(result, Count(i)); // 모든 빌딩 기준
        }
        System.out.println(result);
    }

    public static int Count(int idx) {
        int cnt = 0;

        //오른쪽 - 기울기 증가
        double maxSlope = -1000000000;

        for (int i = idx + 1; i <= N; i++) {
            double slope = (double) (arr[idx] - arr[i]) / (idx - i);

            if (maxSlope < slope) {
                maxSlope = slope;
                cnt++;
            }
        }

        //왼쪽 - 기울기 감소
        double minSlope = 1000000000;
        for (int i = idx - 1; i >= 1; i--) {
            double slope = (double) (arr[idx] - arr[i]) / (idx - i);

            if (minSlope > slope) {
                minSlope = slope;
                cnt++;
            }
        }
        return cnt;
    }
}