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

https://www.acmicpc.net/problem/1027

1027번: 고층 건물

풀이

가장 많은 고층 건물이 보이는 건물을 구하고, 거기서 보이는 건물의 수를 출력하라.

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

 

A와 B를 이은 선분의 기울기를 따져보면 쉽게 문제를 해결할 수 있다.

사실 필자도 기울기를 어떻게 구하는건지 몰라서 검색해봤다.

 

건물 A와 건물 B를 이은 선분의 기울기를 구하기 위해선 두 건물간의 거리와 각 건물의 높이를 알아야한다.

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

기울기 구하는 방법을 알았다면 한 가지 더 생각할 것이 있다.

바로, 임의의 건물에서 왼쪽을 탐색하는 것과 오른쪽을 탐색했을 때를 생각해봐야한다.

idx = 11 (12번째 건물)

1. 왼쪽 오른쪽 두 개의 탐색 모두 첫 번째 건물은 무조건 보인다. (cnt = 2)

2. 왼쪽 탐색 (기울기가 감소해야함)

  2-1. 9번째 건물과 10번째 건물을 비교.

  $\frac{7-2}{11-9}$ vs $\frac{7-5}{11-10} $ = 2.5 vs 2.0 로 9번째 건물의 기울기가 더 큼. (11번째 건물에서 9번째 건물은 보이지 않음)

 

  2-2. 8번째 건물과 9번째 건물을 비교.

  $\frac{7-4}{11-8}$ vs $\frac{7-2}{11-9}$ = 1.0 vs 2.5 로 8번째 건물의 기울기가 더 작음. (11번째 건물에서 8번째 건물은 보임)

 

3. 오른쪽 탐색 (기울기가 증가해야함)

  3-1. 12번째 건물과 13번째 건물 비교.

  $\frac{7-3}{11-12}$ vs $\frac{7-1}{11-13}$ = -4.0 vs -3.0 로 13번째 건물의 기울기가 더 큼. (11번째 건물에서 13번째 건물은 보임)

 

 

<최종코드>

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

public class Main {
    static int[] map;
    static int N;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        map = new int[N];
        
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            map[i] = Integer.parseInt(st.nextToken());
        }
        
        int ans = 0;
        for (int i=0; i<N; i++) {
            ans = Math.max(ans, Count(i));
        }
        
        System.out.println(ans);
    }
    
    public static int Count(int idx) {
        int cnt = 0;
        double tmp = 0;
        
        // 왼쪽
        for (int i=idx-1; i>=0; i--) {
            double slope = (double) (map[idx] - map[i]) / (idx - i);
           
            if (i == idx-1 || tmp > slope) {
                cnt++;
                tmp = slope;
            }
        }
        
        // 오른쪽
        for (int i=idx+1; i<N; i++) {
            double slope = (double) (map[idx] - map[i]) / (idx - i);
            
            if (i == idx+1 || tmp < slope) {
                cnt++;
                tmp = slope;
            }
        }
        
        return cnt;
    }
}