백준 1027 - 고층 건물

문제 설명

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 빌딩의 높이가 주어질 때 한 빌딩에서 보이는 건물의 최대 개수를 구하는 것이다.

빌딩이 보이는 조건은 두 건물의 지붕을 이었을 때, 중간에 건물이 접하거나 넘지 않아야 한다.

문제는 두 가지로 요약할 수 있다.

• 비교할 두 건물을 정하기
• 두 건물 사이 중간 건물들이 접하는지 확인하기

 

우선, 비교할 두 건물을 정하는 것은 자신을 제외한 모든 건물들과 비교를 해야 한다.

근처에 건물이 보이지 않더라도 멀리 있는 건물이 보일 수 있기 때문이다.

따라서, $O(N^2)$의 시간 복잡도를 가지게 된다.

N이 50이하이기 때문에 충분히 가능한 범위이다.

 

이제 두 번째인 두 건물 사이 중간 건물들을 확인하는 과정을 진행해야 한다.

이는 문제에 힌트가 나와있다.

"건물을 선분으로 나타낸다."

즉, 건물은 넓이를 가지지 않는다는 것이다.

따라서, 위에서 선정한 두 건물의 지붕을 두 점으로 나타내는 방정식을 구할 수 있다.

double slope = double(buildings[end] - buildings[start]) / (end - start);
double value = slope * (i - start) + buildings[start];

기울기와 x좌표를 모두 알고 있기 때문에 방정식의 y좌표를 구할 수 있고 y좌표보다 실제 빌딩의 높이가 높거나 같다면 해당 건물에 가려져 보이지 않는 건물이 된다.

 

이렇게 모든 건물을 탐색한 뒤, 보이는 건물의 최대값을 구하면 정답을 구할 수 있다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N;
vector<long long> buildings;

bool check(int start, int end)
{
    if (end < start) swap(start, end);
    double slope = double(buildings[end] - buildings[start]) / (end - start);

    for (int i = start + 1; i < end; i++)
    {
        double value = slope * (i - start) + buildings[start];
        if (buildings[i] >= value) return false;
    }

    return true;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    buildings.resize(N);

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

    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        int current = 0;

        for (int j = 0; j < N; j++)
        {
            if (i == j) continue;
            if (check(i, j)) current++;
        }

        ans = max(ans, current);
    }

    cout << ans;

    return 0;
}

---