문제 접근

일단 빌딩은 50개 밖에 없다.... 브루트 포스다. 그런데 어떻게 해야 효율적으로 접근할 수 있을까?

기준 i위치 빌딩에 대해, 그 좌측에 있는 빌딩 j와의 기울기를 다음과 같이 정의하자. ( 단, 0<=j<i )

• double degree = (double)(buildings[i] - buildings[j]) / (i - j);

그리고, 기준 i위치 빌딩에 대해, 그 우측에 있는 빌딩 j와의 기울기는 다음과 같이 정의해보자. ( 단, i<j<N )

• double degree = (double)(buildings[j] - buildings[i]) / (j - i);

생각해보기

• i 빌딩 관점에서 자신의 좌측 빌딩들이 보이려면, 그 이전에 나왔던 빌딩과의 기울기보다 기울기가 더 작아져야 한다.
• i 빌딩 관점에서 자신의 우측 빌딩들이 보이려면, 그 이전에 나왔던 빌딩과의 기울기보다 기울기가 더 커져야 한다.

이걸 이해한다면 풀이는 쉬워진다.

문제 풀이

import java.util.*;
import java.io.*;

public class Main {
    static int N;
    static int[] buildings;

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

        int max = 0;
        for (int i = 0; i < N; i++) {
            int count = 0;
            double leftDegree = Integer.MAX_VALUE; // 초기는 정말 큰 값으로
            for (int j = i - 1; j >= 0; j--) {
                double degree = (double)(buildings[i] - buildings[j]) / (i - j);
                if (degree < leftDegree) {
                    count++;
                    leftDegree = degree;
                }
            }

            double rightDegree = Integer.MIN_VALUE; // 초기는 정말 작은 값으로
            for (int j = i + 1; j < N; j++) {
                double degree = (double)(buildings[j] - buildings[i]) / (j - i);
                if (degree > rightDegree) {
                    count++;
                    rightDegree = degree;
                }
            }
            max = Math.max(max, count);
        }

        System.out.println(max);
    }
}

주의 사항) 나는 이 문제를 풀다가 잠깐 막혔는데,,, 이유는 기울기를 구할때 정수형 타입으로 받아버렸다... 기울기 같은 소수점도 중요한 경우는 반드시 실수형으로 해주자..