[백준] 1027번 고층 건물 (Java)

0. 출처

백준 1027번 문제입니다.

 

1. 문제

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

(1) 입력

첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

(2) 출력

첫째 줄에 문제의 정답을 출력한다.

 

2. 문제 풀이

(1) 문제 풀이 방법

A에서 B빌딩을 보기 위해서는 A와 B의 지붕을 잇는 선분 상에 A의 지붕, B의 지붕을 제외한 다른 점이 있으면 안됩니다.

그림으로 보명 1번 빌딩에서 2번 빌딩은 볼 수 있지만, 1번 빌딩에서 5번 빌딩은 볼 수 없는 것이죠!

반대로 생각했을 때도 같습니다. 2번 빌딩에서 1번 빌딩을 볼 수 있지만, 5번 빌딩에서 1번 빌딩은 볼 수 없습니다.

 

이를 활용해서 1번 빌딩부터 쭉 확인해보며 볼 수 있는 빌딩을 체크합니다. check[1][2] = true라면 자동으로 check[2][1]=true가 되는 것입니다.

 

선분 위에 다른 빌딩이 걸리는지를 확인하는 방법은 가로가 1 증가할 때마다 세로의 증가 폭을 계산하면 됩니다.

예를 들어 그림의 1번 빌딩과 5번 빌딩을 보면 가로가 1 증가할 때 세로도 1 증가합니다. 선분의 기울기가 1인 것이죠!

1번의 높이에 (증가폭 * 가로 차이)를 더한 값이 해당 빌딩의 높이보다 크면 지붕 위를 지나가는 것이므로 통과 가능하게 됩니다. 

(말로 적는게 어렵네요.. 코드로 보시죠!)

double gap = (double)(h[j]-h[i]) / (double)(j-i); // 증가폭을 계산합니다.
int idx = 1;
boolean able = true;

while(i+idx<j) {
    if(((double)h[i] + ((gap * (double)idx))<=(double)h[i+idx])){
    // 만약 증가폭을 더한 값이 원래 높이보다 낮거나 같다면 빌딩을 볼 수 없습니다.
        able = false;
        break;
    }
    idx++;
}

이후 사이에 걸리는 값이 없다면 빌딩을 볼 수 있는 것이므로 check 배열 값을 true로 바꿔줍니다.

앞에서 설명한 것 처럼 1번 빌딩이 2번 빌딩을 볼 수 있으면, 2번 빌딩은 무조건 1번 빌딩을 볼 수 있으므로 같이 업데이트해 줍니다.

if(able) {
    check[i][j] = true;
    check[j][i] = true;
}

(2) 코드(Java)

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

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

        int[] h = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            h[i] = Integer.parseInt(st.nextToken());
        }
        
        boolean[][] check = new boolean[N][N];
        for(int i=0; i<N; i++) {
            for(int j=i+1; j<N; j++) {           
                double gap = (double)(h[j]-h[i]) / (double)(j-i);
                int idx = 1;
                boolean able = true;
                while(i+idx<j) {
                    if(((double)h[i] + ((gap * (double)idx))<=(double)h[i+idx])){
                        able = false;
                        break;
                    }
                    idx++;
                }
                
                if(able) {
                    check[i][j] = true;
                    check[j][i] = true;
                }
            }
        }
        
        int max = 0;
        for(int i=0; i<N; i++) {
            int count = 0;
            for(int j=0; j<N; j++) {
                if(check[i][j]) count++;
            }
            max = Math.max(count, max);
        }

        System.out.println(max);
        br.close();
    }
}

(3) 결과