백준 1027번 고층 건물

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

public class HighRiseBuilding {
    static int[] height;
    static int N;
    static int count =0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        height = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            height[i] = Integer.parseInt(st.nextToken());
        }
        int max = 0;
        for (int i = 0; i < N; i++) {
            count = 0;
            left(i);
            right(i);
            max = Math.max(max,count);
        }
        System.out.println(max);
    }
    public static void left(int index){
        if(index-1<0) return;
        double down = Integer.MAX_VALUE;
        double up  = Integer.MIN_VALUE;
        for (int i = index-1; i >= 0; i--) {
            int heightDiff = height[index] - height[i];

            double tan = (double) Math.abs(heightDiff) /(index-i);
            if(tan<down&&heightDiff>=0){
                down = tan;
                count++;
            }
            else if(tan>up&&heightDiff<0) {
                up = tan;
                down = 0;
                count++;
            }
        }
    }
    public static void right(int index){
        if(index+1>=N) return;
        double down = Integer.MAX_VALUE;
        double up  = Integer.MIN_VALUE;
        for (int i = index+1; i <N; i++) {
            int heightDiff = height[index] - height[i];
            double tan = (double) Math.abs(heightDiff) /(i-index);
            if(tan<down&&heightDiff>=0){
                down = tan;
                count++;
            }
            else if(tan>up&&heightDiff<0) {
                up = tan;
                down = 0;
                count++;
            }
        }
    }
}

풀이 방법

전체 코드의 구조는 현재 위치의 건물에서 왼쪽에 위치한 건물, 오른쪽의 위치한 건물 중 조건에 해당하는 건물을 세고, 완전탐색 방식으로 탐색하여 조건에 맞는 건물 중 최댓값을 구한다.

두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다

해당 조건에 부합하려면, 건물끼리의 tan값을 비교해야 한다.
📢tan = 건물의 높이(height) / 현재 건물, 비교건물까지의 가로 거리(index-i)

1. 내 위치 보다 낮은 건물들을 비교할 경우, tan값이 직전에 비교한 건물의 tan값보다 낮아야 한다.(접하면 안되므로 tan값이 같아서도 안됨)

2. 내 위치 보다 높은 건물들을 비교할 경우, tan값이 직전에 비교한 건물의 tan값보다 높아야한다.
   👉이때, 나보다 높은 건물이후, 낮은건물이 다시 등장해봤자, 어차피 보이지 않는다. 따라서, 나보다 높은 건물이 한번 나왔다면, 낮은 건물 비교할때 사용하는 down(tan)값을 0으로 지정하여, 이후 낮은 건물은 비교하지 않는다.

후기

tan값의 비교와 그 안에서 고려해야할 추가조건을 통해, 조건에 부합하는 건물을 완전탐색을 통해 센다.
고려해야할 조건을 잘 생각해야만 구현할 수 있는 문제인것 같다.