고층 건물

알고리즘 구분 : 브루트포스, 수학, 기하학

문제

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 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

문제 풀이

문제에서 가장 많은 고층 빌딩이 보이는 빌딩을 찾고, 그 수를 출력하라고 했으므로, 완전 탐색을 통해 가능한 모든 수를 찾고 이를 비교하는 과정을 거쳐야 한다.
그렇기에 나는 삼중 반복문을 사용하였다. 빌딩의 수는 최대 50이고,
첫 번째 반복문 : 지민이 서있는 빌딩
두 번째 반복문 : 보려고 하는 빌딩
세 번째 반복문 : 서있는 빌딩과 보려고 하는 빌딩 사이에 존재하는 빌딩들
로 구성하여, 지민가 서있는 빌딩에서 보려고 하는 빌딩 사이에서 해당 빌딩을 보는데 방해하는 다른 빌딩이 있는지 체크하고자 하였다.
이 과정의 시간 복잡도는 최대 O(N^3)인데, N의 최댓값은 50이므로 최대 125,000정도의 연산이 진행되기에 TLE는 발생하지 않을 것으로 판단하였다.
빌딩을 보는 것을 방해하는 지 여부를 판단하는 것은 기울기를 이용하였다.
기울기를 구한 뒤에, 특정 Idx마다 빌딩이 어느 높이라면 방해하게 되는지를 계산하여 이를 만족하는지를 확인하는 조건문을 통하여 일일이 확인해주는 방식으로 구현하였다.

처음에 기울기를 아무 생각 없이 int형으로 선언하여 한참 헤매기도 하였다. 기울기가 분수가 나올 수 있으므로 double형으로 선언하는 것을 잊지 말아야겠다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int n;
int high[51];
int solve();

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

    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> high[i];
    }

    if(n == 1) {
        cout << 0 << endl;
    }
    else if(n == 2) {
        cout << 1 << endl;
    }
    else {
        cout << solve() << endl;
    }

    return 0;
}

int solve() {
    int result = 0;

    for(int now = 0; now < n; now++) {
        int temp = 0;
        for(int i = 0; i < n; i++) {
            if(i == now) {
                continue;
            }

            // 기울기 확인
            double slope = double(abs(high[now] - high[i])) / abs((now - i));
            
            if(high[now] > high[i]) {
                slope = (-1) * slope;
            }

            if(i < now) {
                bool check = true;
                for(int j = now - 1; j > i; j--) {
                    if(high[now] + (slope * abs(now - j)) <= high[j]) {
                        check = false;
                        break;
                    } 
                }

                if(check) {                    
                    temp++;
                }
            }
            else {
                bool check = true;
                for(int j = now + 1; j < i; j++) {
                    if(high[now] + (slope * abs(now - j)) <= high[j]) {
                        check = false;
                        break;
                    } 
                }    

                if(check) {
                    temp++;
                }
            }
        }
        result = max(temp, result);
    }

    return result;
}

• 문제 출처 : https://www.acmicpc.net/problem/1027
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.