백준 1027번 고층건물 G4 - 브루트포스

 

안풀려서 엑셀로 만들어서. .슥슥

 

하필 또 술먹고 풀어서 머리가 많이 안굴러가 고생한 문제다.

가장 많은 빌딩을 볼 수 있을때 몇개나 볼 수 있는지 구하는 문제이다.

처음에는 어떤 기준으로 보이려나 감이 안잡혀서 그림으로 표현해서 해결했다.

 

답은 기울기 였다. 

 

현재 내가 있는 빌딩에서 바라보려는 빌딩의 사이가 막혀있다면 볼 수 없으니 기울기를 통해 이를 판단했다.

기울기 판단은 (현재 높이 - 판단할 빌딩 높이)  / (현재 위치 idx - 판단할 빌딩 idx) 로 해주었다.

 

위 계산 방식으로 판단하면 왼쪽의 경우 기울기가 기준보다 크다면 볼 수 없고,

오른쪽의 경우 기울기가 기존보다 작다면 안보일것이다.

 

먼저 노랑색 포인트를 기준으로 예시를 들겠다.

현재 7높이의 위치하고 있고, idx는 12번이다.

양쪽은 언제나 확인할 수 있으며 그 다음 빌딩부터는 기울기를 갱신해 가면서 확인 할 수 있는지 체크한다.

 

왼쪽 : 기울기가 작아져야 함

 

왼쪽에 있는 높이 5의 빌딩은 idx 11이 되겠다.

높이 5의 빌딩과의 기울기는 2 이다. (7 - 5) / (12 - 11)

볼 수 있으므로 기준 기울기를 갱신해준다. slope = 2, cnt ++

높이 2의 빌딩과의 기울기는 2.5 이다. (7 - 2) / (12 - 10)

기준 기울기보다 높으므로 보이지 않는다. 기울기를 갱신하지 않는다.

반복 ...

 

오른쪽 : 기울기가 커져야 함

 

오른쪽에 있는 높이 3의 빌딩은 idx 12이 되겠다.

높이 3의 빌딩과의 기울기는 -4 이다. (7 - 3) / (12 - 13)

볼 수 있으므로 기준 기울기를 갱신해준다. slope = -4, cnt ++

높이 1의 빌딩과의 기울기는 -3 이다. (7 - 1) / (12 - 14)

볼 수 있으므로 기준 기울기를 갱신해준다. slope = -3, cnt ++

반복 ...

 

import java.io.*;
import java.util.*;
 
class Main { // Boj_1027_고층빌딩
    public static int[] building;
    public static int N, answer;
 
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        answer = 0;
        building = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int Tc = 0; Tc < N; Tc++) {
            building[Tc] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < N; i++) {
            bruteForce(i);
        }
        System.out.println(answer);
    }
 
    public static void bruteForce(int idx) {
        int cnt = 0;
        double leftSlope = Integer.MAX_VALUE;
        double rightSlope = Integer.MIN_VALUE;
 
        // left
        for (int i = idx - 1; i >= 0; i--) {
            double incline = (double) (building[idx] - building[i]) / (idx - i);
            if (incline < leftSlope) {
                cnt++;
                leftSlope = incline;
            }
        }
 
        // right
        for (int i = idx + 1; i < N; i++) {
            double incline = (double) (building[idx] - building[i]) / (idx - i);
            if (incline > rightSlope) {
                cnt++;
                rightSlope = incline;
            }
        }
 
        answer = Math.max(answer, cnt);
    }
}