[BOJ/C++] 1027::고층 빌딩

고층 건물

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	8877	3732	3216	45.207%

문제

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

---

예제 입력 1 복사

15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5

예제 출력 1 복사

7

예제 입력 2 복사

1
10

예제 출력 2 복사

0

예제 입력 3 복사

4
5 5 5 5

예제 출력 3 복사

2

예제 입력 4 복사

5
1 2 7 3 2

예제 출력 4 복사

4

예제 입력 5 복사

10
1000000000 999999999 999999998 999999997 999999996 1 2 3 4 5

예제 출력 5 복사

6

---

후기

이번 문제는 이해가 잘 안되서 다른 분들의 설명을 통해 이해했다.

 

가장 처음 생각든 해결방안은 각 빌딩마다 양쪽 방향으로 기울기를 보는 것이다.

 

현재 빌딩 기준으로 시야에 보이는 빌딩은 다음과 같다.

왼쪽 방향은 갈수록 기울기가 작아져야 시야에 보이는 빌딩이다.

오른쪽 방향은 갈수록 기울기가 커져야 시야에서 보이는 빌딩이 된다.

 

아래 그림을 보면 다른 빌딩에 가려져 다음 빌딩이 안보이는 것을 알 수 있다.

 

 

그런데, 다른 블로그를 보다 훨씬 좋아보이는 방법을 보았다.

 

순차 탐색은 동일하지만, 나의 생각과 달리 각 빌딩마다 양 옆을 탐색하지 않는다.

 

이 알고리즘에서 핵심은 다음과 같다.

 

왼쪽부터 오른쪽으로 순차 탐색하며, 현재 건물과 오른쪽 건물이 서로 볼 수 있다면 다음 차례가 왔을 때 다시 왼쪽을 확인할 필요가 없다.

 

즉, 가장 왼쪽 빌딩에서 시작하여 오른쪽 방향으로 기울기를 계산하며 서로 보이는 빌딩과 현재 빌딩 둘다 보이는 빌딩 개수를 증가시키면 양방향 탐색을 할 필요가 없다는 것이다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int HighestBuilding(int buildings[], int number);

int main(void) {
    ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

    int number = 0;
    cin >> number;
    int buildings[number];

    for (int k = 0; k < number; k++) {
        cin >> buildings[k];
    }

    cout << HighestBuilding(buildings, number) << '\n';

    return 0;
}

int HighestBuilding(int buildings[], int number) {
    int maxView = 0;
    int buildingCount = number;
    int buildingView[number] = { 0, };

    for (int k = 0; k < buildingCount; k++) {
        double maxSlop = -1000000000;
        for (int j = k + 1; j < buildingCount; j++) {
            double slop = (double)(buildings[j] - buildings[k]) / (j - k);
            cout << "From " << k << "(" << buildings[k] << ") to " << j << "(" << buildings[j] << ") : " << maxSlop << ", " << slop << endl;
            // 현재 빌딩과 목표 빌딩이 서로 보이는 관계면 서로 보이는 빌딩 개수 증가
            if (slop > maxSlop) {
                buildingView[k]++;
                buildingView[j]++;
                maxSlop = slop;
            	cout << "From " << k << "(Height=" << buildings[k] << ") to " << j << "(Height=" << buildings[j] << ") : " << maxSlop << ", " << slop << endl;
            }
        }
    }

    for (int k = 0; k < buildingCount; k++) {
        cout << buildingView[k] << " ";
        maxView = max(maxView, buildingView[k]);
    }
    cout << endl;

    return maxView;
}

5
1 2 7 3 2
From 0(Height=1) to 1(Height=2) : -1e+09, 1
Current Building 0 View : 1, Building on right 1 : 1
From 0(Height=1) to 2(Height=7) : 1, 3
Current Building 0 View : 2, Building on right 2 : 1
From 0(Height=1) to 3(Height=3) : 3, 0.666667
From 0(Height=1) to 4(Height=2) : 3, 0.25
From 1(Height=2) to 2(Height=7) : -1e+09, 5
Current Building 1 View : 2, Building on right 2 : 2
From 1(Height=2) to 3(Height=3) : 5, 0.5
From 1(Height=2) to 4(Height=2) : 5, 0
From 2(Height=7) to 3(Height=3) : -1e+09, -4
Current Building 2 View : 3, Building on right 3 : 1
From 2(Height=7) to 4(Height=2) : -4, -2.5
Current Building 2 View : 4, Building on right 4 : 1
From 3(Height=3) to 4(Height=2) : -1e+09, -1
Current Building 3 View : 2, Building on right 4 : 2
2 2 4 2 2 
4

---

참고자료

[BOJ] 백준 1027 고층건물 c++ (브루트포스, 기하학)