백준 - 고층건물(1027)

❤️문제링크

접근법

처음에는 가장 큰 빌딩을 구한 후, 왼쪽과 오른쪽으로 나뉘어서 구하려고 했지만 해당 방법으로 하면 코드가 더 복잡해질 것이 예상되어 아래와 같이 구하게 되었다.

1. 처음부터 끝까지 오른쪽 빌딩만 본다.
2. 바로 옆 빌딩은 무조건 볼 수 있기 때문에 for문 진입 전 미리 ++를 해준다.
   (양방향으로 ++를 해줘야 한다.)
3. 바로 옆 빌딩과의 기울기를 기준선으로 잡고, 그 다음(즉 오른쪽 방향으로 옆옆 빌딩부터 시작) for문으로 진입하여 새로운 빌딩과의 기울기가 기준선의 기울기보다 더 크다면, 기준선을 갱신 후 볼 수 있는 빌딩으로 간주한다.

코드

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

public class Main {
    static int [] building;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        building = new int[N+1];
        int [] sight = new int[N+1];

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

        for(int i=1; i<N; i++){
            double standardSlope = findSlope(i, i+1);
            sight[i]++;
            sight[i+1]++;
            for(int j=i+2; j<=N; j++) {
               double newSlope =  findSlope(i, j);
               if(standardSlope < newSlope) {
                   standardSlope = newSlope;
                   sight[i]++;
                   sight[j]++;
               }
            }
        }

        int answer = 0;
        for(int i=1; i<=N; i++){
            answer = Math.max(answer, sight[i]);
        }
        System.out.println(answer);
    }

    static double findSlope(int j, int i) {
        return (double) (building[j] - building[i]) / (j - i);
    }
}