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

[Gold IV] 고층 건물 - 1027

문제 링크

문제 설명

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

입력

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

출력

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

 

---

접근

보자마자 기울기를 활용해야 한다는 생각을 했다. 처음에는 빌딩 i를 순회하며, 그 빌딩에서 다른 빌딩까지의 기울기의 최댓값, 최솟값등을 활용하려 했다. 하지만 중간에 가려졌다가 다시 보였다가 하는 구간이 생길 수 있음을 인지하였다.

 

접근 방식을 바꿨다. 결국 완전탐색을 해야한다고 생각했다. 빌딩 i를 정하고, i가 아닌 j 빌딩에 대해서 i와 j 사이를 전부 탐색하며 장애물이 생기는지 체크하는 방식이다. i가 j보다 클 경우와 작을 경우에 기울기의 방향이 바뀌므로 케이스를 나눠서 생각해야했다. 이렇게 풀면 될거라고 생각했는데 이상하게도 답이 계속 나오지 않았다.

 

나눗셈 연산을 오랜만에 했더니 형변환을 깜빡한 것이었다.
(float)로 명시적 형변환을 해주었지만 여전히 답이 나오지 않았다.
문제 조건을 다시 살펴보니 건물의 높이가 10^9 까지 주어진다는 것을 알았다. 왠지 (double) 을 사용해야할 것 같았다.
근데 이런저런 생각을 하다보니 나누는 과정 자체가 좀 불안정한 거 같아서 그냥 곱연산으로 처리하고 (long)으로 형변환을 해주었다.

 

---

전체코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		int max = 0;
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		for (int i = 0; i < n; i++) {
			int cnt = 0;
			for (int j = 0; j < n; j++) {
				if (i == j)
					continue;
				boolean flag = true;
				for (int k = i + 1; k < j; k++) {
					if ((long) (arr[k] - arr[i]) * (j - i) 
                   	 		>= (long) (arr[j] - arr[i]) * (k - i)) {
						flag = false;
						break;
					}
				}
				for (int k = i - 1; k > j; k--) {
					if ((long) (arr[k] - arr[i]) * (j - i) 
                    			<= (long) (arr[j] - arr[i]) * (k - i)) {
						flag = false;
						break;
					}
				}
				if (flag)
					cnt++;
			}
			max = Math.max(cnt, max);
		}
		System.out.println(max);
	}
}