[BOJ] 1027 - 고층 건물 (Java)

접근법

생각보다 까다로웠던 문제.
처음 접근은 가장 긴 오름차순 배열의 길이를 구하는 문제인 줄 알았다.
이 접근법은 네 가지의 문제가 있다.

1. 내림차순도 생각해야 한다는 점 ( 위에서 내려다보는 )
2. 마냥 오름차순이나 내림차순이라고 해도 건물에 가릴 수도 있다는 점
3. 몇 건물이 가리더라도 뒷 건물이 매우 크면 또 보일 수 있다는 점
4. 하나의 건물에서 좌, 우로 볼 수 있다는 점

이 네 가지를 유념하면서 문제를 바라보면 다르게 생각할 수 있다.
바로 각도다.
하나의 건물을 기준으로 바라보는 각도가 밑에서 위로 올라가면서 몇 개의 건물을 볼 수 있는지를 찾으면 되는 문제
그래서 각도가 올라가면서 각도의 최댓값을 갱신할 때, 갯수를 세어 최대 갯수를 출력한다.

---

코드

package boj;

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

public class BOJ_1027_고층_건물 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;

	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());

		int[] buildings = new int[N];
		for (int i = 0; i < N; i++) {
			buildings[i] = Integer.parseInt(st.nextToken());
		}

		int maxCnt = 0;

		for (int i = 0; i < N; i++) {
			double degree = 1000000000;
			int tCnt = 0;

			for (int j = i - 1; j >= 0; j--) {
				if (degree > (double) (buildings[j] - buildings[i]) / (j - i)) {
					degree = (double) (buildings[j] - buildings[i]) / (j - i);
					tCnt++;
				}
			}
			degree = -1000000000;
			for (int j = i + 1; j < N; j++) {
				if (degree < (double) (buildings[j] - buildings[i]) / (j - i)) {
					degree = (double) (buildings[j] - buildings[i]) / (j - i);
					tCnt++;
				}
			}
			maxCnt = Math.max(tCnt, maxCnt);
		}
		System.out.println(maxCnt);

	}
}

결과

메모리 시간 언어

14268KB

136ms

Java