백준 1027번 : 고층 건물 (자바)

728x90

문제

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

---

입력

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

---

출력

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

🔵 풀이

N이 50이하이기 때문에 완전탐색이 가능하다고 판단하였습니다. 그래서 각 건물을 기준으로 몇개의 건물을 볼수 있는지 탐색했습니다. 처음에는 단순히 건물의 높이의 증가 감소 여부로 판단하였으나 실패하였고 기울기를 통해 판별해야 했습니다. 그래서 float형으로 기울기를 검사하며 가장 많이 볼 수 있는 건물을 구했습니다.

 

 

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

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

    for (int i=0; i<N; i++){
      arr[i] = Integer.valueOf(stringTokenizer.nextToken());
    }

    for (int i=0; i<N; i++){
      int one = i-1;
      float oneBefore = Integer.MAX_VALUE;
      int two = i+1;
      float twoBefore = Integer.MIN_VALUE;
      int count = 0;

        while (one>-1||two<N){

          if (one>-1&&oneBefore>(float)(arr[i]-arr[one])/(float)(i-one)){
            oneBefore = (float)(arr[i]-arr[one])/(float)(i-one);
            count++;
          }

          if (two<N&&twoBefore<(float)(arr[two]-arr[i])/(float)(two-i)){
            twoBefore = (float)(arr[two]-arr[i])/(float)(two-i);
            count++;
          }

          one--;
          two++;

      }
        answer = Math.max(answer,count);
    }
    System.out.println(answer);
  }
}