[Algorithm] 1027 - 고층 건물

목차

---

1. 문제 설명

2. 접근 방식

3. 코드

 

 

 

 

 

1. 문제 설명

---

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

 

문제는 비교적 간단하다. 

빌딩들의 높이가 주어졌을 때 가장 많이 보이는 고층 빌딩의 개수를 찾는 것이다. 

빌딩 A에서 빌딩 B를 보려면 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 

 

 

 

2. 접근 방식

---

빌딩의 높이는 계속 달라지고, 앞의 계산 결과를 활용하기 어렵기 때문에 슬라이딩 윈도우나 dp는 고려하지 않았다. 

문제에서 주어진 "빌딩을 보기 위한 조건"은 기울기의 사전적 정의와 유사해보였다.

 

 

좌표 평면에 아래의 입력 예제를 그린 그림이다. 

3 // 빌딩 개수
1 3 2 // 빌딩 높이

 

(1, 1)을 기준으로 볼 때 (2, 3)은 볼 수 있다. (O)

(1, 1)을 기준으로 볼 때 (3, 2)는 볼 수 없다. (X)

빌딩1과 빌딩 3을 연결하는 선분이 다른 고층 빌딩을 지나고 있기 때문이다. 

 

따라서 빌딩1부터 빌딩 N까지는 아래와 같은 규칙을 따른다. 

 

자신을 기준으로 오른쪽 건물들은 기울기가 커져야 볼 수 있다.
자신을 기준으로 왼쪽 건물들은 기울기가 작아져야 볼 수 있다.

 

반복문으로 빌딩을 하나씩 검사하며, 다음의 조건을 만족하면 볼 수 있는 건물로 카운팅한 뒤 max를 구하면 된다. 

이를 코드로 구현해보자.

 

 

 

3. 코드

---

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

// 기울기
// 자신 기준 오른쪽 : 기울기가 커야 보임
// 자신 기준 왼쪽 : 기울기가 작아야 보임
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()); // 빌딩의 수

        int[] buildings = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        int[] dpLeft = new int[N];
        int[] dpRight = new int[N];
        
        for(int i = 0; i < N; i++) {
            float leftMin = Integer.MAX_VALUE;
            float rightMax = Integer.MIN_VALUE;

            // 1. 왼쪽 검사
            for(int j = i - 1; j >= 0; j--) {
                int x = i - j;
                int y = buildings[i] - buildings[j];

                if((float) y / x >= leftMin) continue;

                leftMin = (float) y / x;
                dpLeft[i]++;
            }

            // 2. 오른쪽 검사
            for(int j = i + 1; j < N; j++) {
                int x = i - j;
                int y = buildings[i] - buildings[j];

                if((float) y / x <= rightMax) continue;

                rightMax = (float) y / x;
                dpRight[i]++;
            }
        }

        int max = 0;
        for(int i = 0; i < N; i++) {
            max = Math.max(dpLeft[i] + dpRight[i], max);
        }

        System.out.print(max);
    }
}

 

기울기를 계산할 때는 형 변환에 주의해야 한다. 

dx, dy는 각각 int로 정의되어있다. (정수형)

그런데 기울기는 정수가 아닌 값도 가능하므로 소숫점까지 비교해주고자 y / x는 float으로 캐스팅해주었다.

 

빌딩1 ~ 빌딩N까지 검사한 뒤에는 각 위치별로 볼 수 있는 고층 건물의 개수를 취합하여 max를 계산해주면 된다.