[백준/JAVA] 1027번: 고층 건물

📖 문제

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

 

 

 

💡  풀이 방식

• 브루트포스, 기하학

. 고층 건물이 보이기 위해서는, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접해서는 안 된다.

→ A와 B를 이은 선분의 기울기를 구하고 이를 활용하여 문제를 풀 수 있다.

선분의 기울기 구하는 공식
: 건물 A와 B를 이은 선분의 기울기 = 건물A 높이 - 건물B 높이 / 건물 A와 B의 거리

 

 

- N개의 빌딩을 모두 둘며, 해당 건물에서 볼 수 있는 고층 건물의 수를 구한다. (브루트포스)

  ㄴ 해당 위치의 왼쪽    부분을 탐색할 때는, 기울기가 감소해야 건물이 보인다.

  ㄴ 해당 위치의 오른쪽 부분을 탐색할 때는, 기울기가 증가해야 건물이 보인다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int ans = 0;
        for(int i = 0 ; i < N ; i++) {
            ans = Math.max(ans, solve(i));
        }
        
        System.out.println(ans);
    }
    
    private static int solve(int idx) {
        int cnt = 0;
        double tmp = 0;
        
        // 왼쪽 탐색 - 기울기 감소해야 함
        for(int i = idx-1 ; i >= 0 ; i--) {
            double slope = (double) (arr[idx] - arr[i]) / (idx - i);
            
            if(i == idx-1 || tmp > slope) {
                cnt++;
                tmp = slope;
            }
        }
        
        // 오른쪽 탐색 - 기울기 증가해야 함
        for(int i = idx+1 ; i < N ; i++) {
            double slope = (double) (arr[idx] - arr[i]) / (idx - i);
            
            if(i == idx+1 || tmp < slope) {
                cnt++;
                tmp = slope;
            }
        }
        
        return cnt;
    }
}

 

 

 

➕ 다른 풀이 방식

- 비슷한데  solve 함수를 객체화하지 않고 바로 작성한 풀이

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

---

💦 어려웠던 점

- 기울기를 활용할 생각은 못 했다...

 

 

🧐 새로 알게 된 내용

- 기울기 활용 아이디어,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준]JAVA - 1027번: 고층 건물