백준 1027 - 고층 건물

Minjae An·2024년 1월 30일

ps 그리디 기하 코딩테스트

PS

목록 보기

135/148

문제

https://www.acmicpc.net/problem/1027

풀이

우선 주어진 빌딩을 순서가 $x$ 고 높이가 $y$ 인 $(x,y)$ 꼴의 좌표 형태로 저장할 것을 고려하였다. 문제에서 주어진 $N$ 의 최대가 50이므로, , 그리디 방식으로 모든 두 쌍의 정점 사이 교차 정점이 존재하는 지 확인하는 방식으로도 제한 조건인 1초를 통과할 수 있을 것으로 접근하였다.

비교하려는 기준점을 $(x_1,y_1)$ , 해당 점과 쌍을 이루는 정점을 $(x_2,y_2)$ , 두 정점 사이에 존재하는 정점을 $(x_3,y_3)$ 로 간주하였을 때 다음 절차로 로직을 구성할 수 있다.

$(x_1,y_1)\;,(x_2,y_2)$ 통해 직선의 방정식 $y=ax+b$ 에서 $a,b$ 도출
사이 선분( $x=x_3$ )의 $x_3$ 대입, $y=ax_3+b$ 도출
$(x_3,y_3)$ 에서 $ax_3+b>y_3$ 이면 교차하거나 접점 존재 X, $(x_1,y_1)$ 에서 $(x_2,y_2)$ 관찰 가능
관찰 가능 빌딩 수, 기준점별로 판단하며 최대 관찰 가능 빌딩 수 갱신

유의할 점으론 기울기, Y절편을 저장하는 변수 타입을 double 로 설정하였다는 점이다. double 의 오차는 연산 결과에 그리 중대한 영향을 미치지 않는다. 로직의 시간복잡도는 기준점과 다른 정점간 쌍 형성, 쌍 사이 교차 정점 존재 여부 판단 과정을 포함하여 $O(N^3)$ 으로 수렴한다. 이는 $N=50$ 인 최악의 경우에도 무난히 제한 조건 2초를 통과한다.

코드

import static java.lang.Integer.*;

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = parseInt(br.readLine());
		Point[] points = new Point[N];
		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int x = 1; x <= N; x++) {
			int y = parseInt(st.nextToken());
			points[x - 1] = new Point(x, y);
		}

		int maxAvailPointsCount = -1;
		for (int idx = 0; idx < points.length; idx++) {
			int availPointsCount = getAvailPointsCount(idx, points);
			maxAvailPointsCount = Math.max(maxAvailPointsCount, availPointsCount);
		}

		System.out.println(maxAvailPointsCount);
		br.close();
	}

	static int getAvailPointsCount(int idx, Point[] points) {
		int count = 0;
		Point p1 = points[idx];

		for (int i = 0; i < points.length; i++) {
			if (i == idx)
				continue;

			Point p2 = points[i];
			double slope = getSlope(p1, p2);
			double yIntercept = getYIntercept(slope, p1);

			if (isInterceptLineExist(idx, i, slope, yIntercept, points))
				continue;

			count++;
		}

		return count;
	}

	static double getSlope(Point p1, Point p2) {
		return (p2.y - p1.y) / ((double)(p2.x - p1.x));
	}

	static double getYIntercept(double slope, Point p) {
		return p.y - slope * p.x;
	}

	static boolean isInterceptLineExist(int idx1, int idx2, double slope, double yIntercept, Point[] points) {
		if (Math.abs(idx1 - idx2) == 1)
			return false;

		int minIdx = Math.min(idx1, idx2);
		int maxIdx = Math.max(idx1, idx2);

		for (int i = minIdx + 1; i < maxIdx; i++) {
			Point p = points[i];
			double yValue = slope * p.x + yIntercept;

			if (yValue <= p.y)
				return true;
		}

		return false;
	}

	static class Point {
		int x, y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}