자바 - 백준 1027 / 고층 건물

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

골드4

구현 방법

1. 서 있을 건물을 정한다.

2. 볼 건물을 정한다.

3. 사이 건물들이 시야를 가리는지 확인한다.

  a. 사다리꼴 면접 공식으로 최대 건물 높이를 구합니다.

  b. 큰 사다리꼴 = 사이 건물 높이로 나눠진 사다리꼴 + 사이 건물 높이로 나눠진 사다리꼴

4. 사이 건물들이 시야를 안 가릴 경우, 볼 수 있는 건물수를 하나 늘린다.

 

주의 사항

범위를 주의해야합니다.

최대 높이가 1,000,000,000이기 때문에 계산 과정에서 오버플로우를 조심해야합니다.

 

개선 방법

사다리꼴 면접으로 중간 높이를 구하지 않고, 기울기 차이로 판단 가능합니다.

 

코드

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

/**
 * 백준 1027
 * 고층 건물
 * 골드4
 * https://www.acmicpc.net/problem/1027
 */
public class Boj1027 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

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

            if(i + 1 < N) {
                cnt++;
                for(int j = i + 2; j < N; j++) {
                    int cur = buildings[j];
                    boolean flag = true;
                    for(int k = i + 1; k < j; k++) {
                        double mid = midH(buildings[i], cur, k - i, j - k);

                        if(mid <= buildings[k]) {
                            flag = false;
                            break;
                        }
                    }

                    if(flag) {
                        cnt++;
                    }
                }
            }

            if(i - 1 >= 0) {
                cnt++;
                for(int j = i - 2; j >= 0; j--) {
                    int cur = buildings[j];
                    boolean flag = true;
                    for(int k = i - 1; k > j; k--) {
                        double mid = midH(cur, buildings[i], k - j, i - k);

                        if(mid <= buildings[k]) {
                            flag = false;
                            break;
                        }
                    }

                    if(flag) {
                        cnt++;
                    }
                }
            }

            max = Math.max(max, cnt);
        }

        System.out.println(max);
    }

    public static double midH(int a, int b, int aD, int bD) {

        return (((long) a * bD) + ((long)b * aD)) / (double) (aD + bD);
    }
}