[Algorithm] 백준_고층 건물_1027번 (JAVA)

📝문제

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

문제

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

입력

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

출력

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

---

💡풀이

문제 유형

수학
브루트포스 알고리즘
기하학

 

걸린 시간

70분

 

시간 복잡도

O(N^2)

 

풀이 방법 도출

 

초반엔 직선 방적식을 사용해서 점이 포함되는가를 구현해야하나 잠시 고민했었는데,

결국엔 기울기 문제였다.

 

노트에 이리저리 그려보니

 

왼쪽으로 갈수록 기울기가 작아지면 빌딩이 보이고,

오른쪽으로 갈수록 기울기가 커지면 빌딩이 보이게 된다.

 

이때, 기울기가 소수점을 포함할 수 있으므로, 정수형 대신 float이나 doubel 같은 실수형으로 값을 입력 받는 것이 중요하다.

 

기울기 공식은 다음과 같다.

기울기(m) = (y2 - y1) / (x2 - x1)

 

위 내용을 기반으로 코드로 구현하면 다음과 같다.

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

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[] buildings = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            buildings[i] = Integer.parseInt(st.nextToken());
        }

        int max = 0;

        for (int i = 0; i < N; i++) {
            int answer = 0;
            double left = Integer.MAX_VALUE;
            double right = Integer.MIN_VALUE;

            for (int j = i - 1; j >= 0; j--) {
                double slope = (double) (buildings[j] - buildings[i]) / (j - i);
                if (slope < left) {
                    left = slope;
                    answer++;
                }
            }

            for (int j = i + 1; j < N; j++) {
                double slope = (double) (buildings[i] - buildings[j]) / (i - j);

                if (slope > right) {
                    right = slope;
                    answer++;
                }
            }
            max = Math.max(max, answer);
        }
        System.out.println(max);
    }
}

---

🤔Review

스스로의 힘으로 푼 문제는 늘 자아 효능감을 up 시켜

골4 문제라 더!