[Gold IV] 고층 건물 - 1027

문제 링크

성능 요약

메모리: 14220 KB, 시간: 104 ms

분류

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

제출 일자

2025년 3월 18일 18:33:54

문제 설명

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

입력

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

출력

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

문제 풀이

좌우 건물들의 높이를 이용했다. 기울기의 증감이 일정하게 증가하느냐 감소하느냐를 보면된다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, h[];
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_1027_고층건물/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        h = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            h[i] = Integer.parseInt(st.nextToken());
        }

        int res = 0;
        for(int i=0; i<N; i++) {
            int left = 0, right = 0;

            if(i==0) right = countRight(0);
            else if(i==N-1) left = countLeft(N-1);
            else {
                left = countLeft(i);
                right = countRight(i);
            }

            if(res < left + right) res = left + right;
        }

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

    private int countLeft(int idx) {
        int cnt = 0;

        double a = 1000000001; // 기울기
        for(int i=idx-1; i>=0; i--){
            double new_a = (h[idx] - h[i]) / (double) (Math.abs(idx-i));
            if(new_a < a) {
                cnt++;
                a = new_a;
            }

        }
        return cnt;
    }

    private int countRight(int idx) {
        int cnt = 0;

        double a = -1000000001;
        for(int i=idx+1; i<N; i++){
            double new_a = (h[i] - h[idx]) / (double) (Math.abs(idx-i));
            if(a < new_a) {
                cnt++;
                a = new_a;
            }
        }
        return cnt;
    }
}