baekjoon/Brute_Force
백준 1027번 : 고층건물 자바
Meluu_
2024. 7. 22. 19:51
🧫 문제 분석
✔️ 출처
📖 문제

핵심
사실상 수학문제라고 봐도 과언이 아니라 생각한다.
기울기의 증감을 따져서 비교하면 되는데
빌딩중 하나를 기준으로 생각해보자.
좌측 부분은 기울기가 증가 하는 형태이고
우측 부분은 기울기가 감소하는 형태이다.

대략 이렇게 볼 수 있다.
뒷건물에 대해서는
기울기 최솟값을 저장하고
최솟값보다 기울기가 크다면 그 빌딩은 볼 수 없는 빌딩이다.
앞 건물에 대해서는
기울기 최대값을 저장하고
최댓값보다 기울기가 작다면 그 빌딩은 볼 수 없는 빌딩이다.

문제에서 A-B 빌딩 선분이 다른 빌딩을 지나거나 접하지 않아야한다 했으므로 기울기가 같으면 그 빌딩은 볼 수 없다.
🔅 문제 풀이
import java.io.*;
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 = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] buildings = new int[n+1];
for (int i = 1; i <= n; i++) {
buildings[i] = Integer.parseInt(st.nextToken());
}
int max = 0;
for (int i = 1; i <= n; i++) {
max = Math.max(max, countBuildings(buildings, i));
}
System.out.println(max);
}
private static int countBuildings(int[] arr, int num) {
double gradient = -1000000001;
int count = 0;
// 우측
for (int j = num + 1; j <arr.length; j++) {
// 기울기 구하기
double m = ((arr[j] - arr[num]) / (j - num));
// 최댓값보다 크면 볼 수 있는 건물
// 최댓값 기울기를 갱신
if (gradient < m) {
count++;
gradient = m;
}
}
// 좌측
gradient = 1000000001;
for (int j = num - 1 ; j >= 1; j--) {
double m = (arr[j] - arr[num]) / (j - num);
// 최솟값보다 작다면 볼 수 있는 건물
// 최솟값 기울기를 갱신
if (gradient > m) {
count++;
gradient = m;
}
}
return count;
}
}
다른 사람풀이를 보며 다시 만든 로직
private static int countBuildings(int[] arr, int num) {
double gradient = 0;
int count = 0;
for (int j = num + 1; j <arr.length; j++) {
double m = (double) (arr[j] - arr[num]) / (j - num);
if (j == num + 1 || gradient < m) {
count++;
gradient = m;
}
}
for (int j = num - 1 ; j >= 1; j--) {
double m = (double) (arr[j] - arr[num]) / (j - num);
if (j == num - 1 || gradient > m) {
count++;
gradient = m;
}
}
return count;
}
내 코드보다 훨씬 이해하기 쉽고 깔끔한거같다.
처음 접하는 빌딩은 무조건 보이니까 무조건 +1하고 최댓값, 최솟값을 갱신하는 것이 인상적이다.
❗ 오답노트 / 필요한 지식
- 처음 풀때 for문에 i값을 double로 했는데 왜그랬는지 모르겠다.
- (double) int / int 시 double형으로 제대로 연산된다.