[백준, 1027, 자바] 고층 건물

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

1027번: 고층 건물

1. 문제 핵심

1. 빌딩의 수는 최대 50개.
2. 빌딩의 높이는 최대 10억보다 작거나 같은 수

---

2. 문제 접근

1. 총 빌딩의 수가 50개밖에 되지 않아 완탐으로 한 빌딩과 그 외 나머지 빌딩을 모두 비교하면서 진행해도 괜찮다고 생각했습니다.
2. [현재] 빌딩과 [비교] 빌딩 바닥 사이의 거리 / A빌딩과 B빌딩 꼭지점 사이의 거리 == 기울기 값을 구할 수 있다.
3. 기준 빌딩 왼쪽, 오른쪽 각각 진행하며 각 기울기 값을 비교해서 기울기가 가장 큰 값을 저장하고 해당 기울기보다 큰 기울기가 존재할 때마다 카운트를 증가하고 저장된 기울기를 더 큰 값으로 갱신합니다.

 

---

3. 문제 후기

• 처음엔 cosΘ(밑변/빗변)값을 통해 비교했는데 원하는 값이 나오지 않아서 기울기를 통해 비교해야한다는 도움을 받았습니다.
• 또한 두 빌딩은 서로 보일 수 있기 때문에 굳이 한 빌딩에서 좌, 우로 모두 확인하지 않고, 차례대로 왼쪽에서 오른쪽으로 기준점을 옮기며 검사를 하면 시간 단축이 가능합니다.

---

4. 자바 코드

package _0721.ChungLee;

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

class BOJ_1027_G4_고층건물 {
	static int N;
	static int[] building;
	static int[] visible;

	// 보이는 빌딩 카운팅
	private static void count() {
		// 빌딩이 하나인 경우는 제외하기 위해 N - 1
		for (int i = 0; i < N - 1; i++) {
			visible[i] += 1; // 바로 옆 건물은 무조건 보임
			visible[i + 1] += 1;
			
			//높이 차이
			double slope = building[i + 1] - building[i];
			
			//다다음 빌딩부터 비교
			for (int j = i + 2; j < N; j++) {
				// 기울기 계산 
				double nextSlope = (double) (building[j] - building[i]) / (j - i);
				
				//이전 기울기보다 작거나 같으면 안보이는 것이기 때문에 패스
				if (nextSlope <= slope)
					continue;
				
				//더 크다면 해당 기울기 저장
				slope = nextSlope;
				
				//두 빌딩은 서로 보이는 것이기 때문에 각각 ++
				visible[i]++;
				visible[j]++;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		// 빌딩 정보 저장
		building = new int[N];
		// 빌딩이 보이는지 여부 저장
		visible = new int[N];

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

		count();

		Arrays.sort(visible);
		System.out.println(visible[visible.length - 1]);
	}

}

---

5. 시간

솔루션을 참고했기 때문에 제출하지 않음.