[백준] 고층 건물 (수학)

문제 소개

고층 건물 - 백준 1027번 문제를 정리합니다.
이 문제는 각 고층 빌딩에서 볼 수 있는 다른 빌딩의 수를 구하는 시뮬레이션 문제입니다.
핵심은 두 빌딩 사이를 잇는 직선이 다른 빌딩에 가려지지 않아야 한다는 조건을 만족하는지 확인하는 것입니다.

문제 링크: 고층 건물 - 백준 1027번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 각 빌딩 i에 대해 오른쪽 빌딩 j를 차례로 탐색
2. (i, height[i])와 (j, height[j])를 연결하는 직선의 기울기를 계산
3. 이 기울기가 지금까지 본 것 중 가장 크면 → i와 j는 서로 볼 수 있음
4. 이때 기울기가 maxGradient보다 작거나 같다면 → 중간에 있는 빌딩이 가리는 것

---

해결 과정 및 코드

핵심 아이디어

1. 빌딩 i에서 오른쪽으로 나아가며 j를 만날 때, 직선 기울기 = (높이 차) / (거리 차)
2. 이때 지금까지 본 빌딩 중 가장 높은 기울기(maxGradient)를 저장
3. 현재 기울기 ≤ maxGradient라면 이전에 더 가파른 빌딩이 가리고 있음 → pass
4. 현재 기울기 > maxGradient라면 보임 → cnt[i]++, cnt[j]++, maxGradient 갱신

 

→ 이 과정은 오른쪽 방향만 보면 되지만, 서로 보는 것이므로 cnt[j]++도 필요

코드

시간 복잡도 : O(N²)

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = read();
		int[] buildings = new int[N];
		int[] cnts = new int[N];

		for (int i = 0; i < N; i++) {
			buildings[i] = read();
		}

		for (int i = 0; i < N; i++) {
			double maxGradient = -1e10; // 가장 큰 기울기 저장
			for (int j = i + 1; j < N; j++) {
				double gradient = (buildings[j] - buildings[i]) * 1.0 / (j - i);
				if (gradient <= maxGradient) continue; // 이미 가려짐
				maxGradient = gradient; // 갱신하고 서로 볼 수 있음
				cnts[i]++;
				cnts[j]++;
			}
		}

		int max = 0;
		for (int cnt : cnts) {
			max = Math.max(max, cnt);
		}
		bw.write(Integer.toString(max)); bw.flush();
	}

	public static int read() throws IOException {
		int cur, n = System.in.read() & 15;
		boolean isNegative = (n == 13);
		if (isNegative) n = System.in.read() & 15;
		while ((cur = System.in.read()) > 32) {
			n = (n << 3) + (n << 1) + (cur & 15);
		}
		return isNegative ? -n : n;
	}
}