1027번: 고층건물

• N개의 고층 빌딩이 있다 (N ≤ 50).
• 각 빌딩은 (i, 0)부터 (i, 높이)까지의 선분으로 표현된다.
• 빌딩 A에서 빌딩 B가 보이려면, 두 빌딩의 지붕을 잇는 선분이 다른 어떤 빌딩도 지나거나 접하지 않아야 한다.
• 가장 많은 빌딩이 보이는 빌딩을 찾고, 그 빌딩에서 보이는 빌딩의 수를 출력한다.
• 각 빌딩의 높이는 10^9 이하의 자연수이다.

접근

보이는 조건

A, B, C 빌딩이 있을 때, A에서 C가 보이려면 B가 A와 C를 잇는 선분에 접하거나 겹치면 안된다.
그렇다면 이 선분을 어떻게 표현하고, 선분에 접하거나 겹치는지 어떻게 알 수 있을까?

기울기 비교하기

A-C를 잇는 선분의 기울기 = (A 높이 - C 높이) / A-C 거리
A와 C 사이의 기울기를 이렇게 정의한다면, 동일하게 A와 B 사이의 기울기를 계산할 수 있다.

그리고 A-C 기울기가 A-B 기울기보다 작다면, A-C를 잇는 선분이 A-B를 잇는 선분보다 위에 존재하기 때문에 "보인다"라고 할 수 있다.

가까운 건물부터 비교하기

이제 보이는지 안보이는지를 알 수 있게 되었으므로, 가까운 건물부터 먼건물 순으로 기울기를 확인하면서 기울기가 내림차순이 되는 건물의 숫자를 확인하면 된다.

전부 살펴보기

건물의 수 N이 50으로 매우 작기 때문에 모든 건물에 대해 비교를 수행하면 된다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        
        input(in);
        solve();   
    }
    
    static int nBuilding;
    static int[] height;
    static void input(BufferedReader in) throws IOException {
    	nBuilding = Integer.parseInt(in.readLine());
    	height = new int[nBuilding];
    	StringTokenizer tokens = new StringTokenizer(in.readLine());
    	for(int i = 0; i < nBuilding; i++) {
    		height[i] = Integer.parseInt(tokens.nextToken());
    	}
    }
    
    static void solve() {
    	int max = 0;
    	
    	for(int i = 0; i < nBuilding; i++) {
    		int cur = height[i];
    		
    		int cnt = 0;
    		double prev = Double.MAX_VALUE;
    		for(int j = i-1; j >= 0; j--) {
    			double dist = i - j;
    			double tilt = (cur - height[j])/dist;
    			if(tilt < prev) {
    				prev = tilt;
    				cnt++;
    			}
    		}
    		
    		prev = Double.MAX_VALUE;
    		for(int j = i+1; j < nBuilding; j++) {
    			double dist = j - i;
    			double tilt = (cur - height[j])/dist;
    			if(tilt < prev) {
    				prev = tilt;
    				cnt++;
    			}
    		}
    		
    		max = Math.max(max, cnt);
    	}
    	
    	System.out.println(max);
    }
}

회고

• 처음 문제를 볼 때는 가장 긴 증가하는 수열 문제와 비슷해보이기도 했지만, 기울기를 활용해야하는 문제라서 높이차와 거리에 따라 증감이 의미 없을 수 있어서 완전 다른 문제였다.