boj 1027: 고층 건물

문제 조건

고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면,

두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. => 기울기를 생각해 주어야 한다.

가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 문제이다.

 

백준에 나와있는 예시를 그려보면 아래와 같고, index=12일 때, 볼 수 있는 빌딩의 경우 선을 연결해 보면

빌딩을 기준으로 왼쪽으로 갈때나 오른쪽으로 가면서 볼 때 기울기가 커져야 한다.

15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int building[] = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			building[i] = in.nextInt();
		}

		System.out.println(checkAllBuilding(building, n));
	}

	public static int checkAllBuilding(int[] building, int n) {
		int max = 0;

		for (int i = 1; i <= n; i++) {
			int sum = calcGradient(building, i, n, 1) + calcGradient(building, i, n, -1);
			max = Math.max(max, sum);
		}

		return max;
	}

	public static int calcGradient(int[] building, int index, int n, int dx) {
		if ((index == 1 && dx < 0) || (index == n && dx > 0)) {
			return 0;
		}

		int num = 1;
		int checkIndex = index + dx;
		long gradientY = building[index] - building[checkIndex];
		long gradientX = index - checkIndex;

		while (true) {
			checkIndex += dx;
			if (checkIndex <= 0 || checkIndex > n) {
				break;
			}

			long nextGradientY = building[index] - building[checkIndex];
			long nextGradientX = index - checkIndex;
			if (isPossible(gradientY, gradientX, nextGradientY, nextGradientX, dx)) {
				gradientY = nextGradientY;
				gradientX = nextGradientX;
				num++;
			}
		}
		return num;
	}

	public static boolean isPossible(long gradientY, long gradientX, long nextGradientY, long nextGradientX, int dx) {
		if (dx > 0) { // 포인터가 오른쪽으로 움직이고 있는 경우 - 기울기가 증가해야 함
			return nextGradientY * gradientX > gradientY * nextGradientX;
		}

		// 포인터가 왼쪽으로 움직이고 있는 경우 - 기울기가 감소해야 함
		return nextGradientY * gradientX < gradientY * nextGradientX;
	}
}

처음에는 double 형으로 기울기를 계산해 주었는데, double의 경우 유효숫자 개수가 정해져 있어서 이렇게 풀면 틀린댄다..

float 형은 부호 (1bit) + 지수 (8bit) + 가수 (23bit) = 32bit = 4byte로 이루어져 있다. => 유효 숫자가 6자리
double 형은 부호 (1bit) + 지수 (11bit) + 가수 (52bit) = 64 bit = 8byte로 이루어져 있다. => 유효 숫자가 15자리