107. 고층 건물 (백준 1027) [JAVA]

문제

문제 링크 : https://www.acmicpc.net/problem/1027

1027번: 고층 건물

문제

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

입력

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

출력

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

풀이

우선 두 빌딩 사이의 직선에 점이 속하는지 아닌지를 판단하는 방법을 생각해야 한다.

수학적으로 풀려고 하면, 높이가 10억까지이기 때문에 double 타입으로도 소숫점을 케어할 수 없을 것이라 생각했다.

a(기준) - b (비교) -c(기준) 를 위해서는 결국 a-c의 기울기와 a-b의 기울기를 비교해야 한다.

a-c와 a-b를 비교하는 방법은 결국 다음과 같이 식으로 정리할 수 있다.

• (ay-by)/(ax-bx) ? (ay-cy)/(ax-cx) -> (ay-by)(ax-cx) ? (ay-cy)(ax-bx)
• -axby + cxby -cxay + axcy + bxay -bxcy ? 0 -> (axcy+bxay+cxby) - (axby+bxcy+cxay) ? 0

 

그렇다면 여기서 고려해야 할 것이 3가지가 있는데

1. 진행방향이 -> , <- 두가지
2. 높은 애만 건물을 볼 수 있는게 아니라, 낮은 애 입장에서도 높은 건물을 볼 수 있다

 

그래서 우선 점 i와, i보다 큰 j를 고정해놓고 그 사이로 하나씩 k의 기울기를 비교한다.

이때 i-j의 기울기보다 i-k의 기울기가 더 크거나 같다면 가운데 점 k가 선을 벗어난 것이기 때문에 종료한다.

이때 i와 함께 j를 늘려줌으로써 2번 상황을 해결한다.

그리고 모든 점에 대해 위 과정을 진행함으로써 1번 문제를 해결한다.

모든 점이 i와 j의 역할을 맡을 수 있기 때문이다. (i일때는 내 오른쪽 검사, j일때는 내 왼쪽 검사)

그리고 높이의 최대가 10억이기 때문에, int가 아닌 long을 사용하는 것을 잊지 말자 !!!!!

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    //(ay-by)/(ax-bx) ? (ay-cy)/(ax-cx)
    //(ay-by)(ax-cx) ? (ay-cy)(ax-bx)
    // -axby + cxby -cxay + axcy + bxay -bxcy
    //(axcy + bxay + cxby) - (axby+bxcy+cxay)

    static int N;
    static long[] map;
    static int[] cache;
    static int answer = 0;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        map = new long[N];
        cache = new int[N];

        for(int i=0; i<N; i++){
            map[i] = Long.parseLong(st.nextToken());
        }

        right();

        for (int a : cache){
            answer = Math.max(a, answer);
        }
        System.out.println(answer);
    }

    public static void right(){

        boolean cont;
        for(int i=0; i<N-1; i++){
            for(int j=i+1; j<N; j++){
                cont = true;
                for(int k=i+1; k<j; k++){
                    if(check(i,j,k) <= 0){
                        cont = false;
                        break;
                    }
                }
                if(cont){
                    cache[i]++;
                    cache[j]++;
                }
            }
        }
    }

    //음수면 기울기 커짐
    static long check(int a, int b, int c){
        return  (long)a*map[c] + (long)b*map[a] + (long)c*map[b] - ((long)a*map[b] + (long)b*map[c] + (long)c*map[a]);
    }
}

 

결과