백준 1027번 [고층 건물](C++) -yes6686- 티스토리

백준 문제 풀이: 1027 (고층 건물)

---

문제 링크: https://www.acmicpc.net/problem/1027

문제 설명:

좌우로 고층 건물이 일렬로 배치되어 있습니다. 특정 건물에서 다른 건물이 보이려면, 두 건물을 잇는 직선이 그 사이에 있는 건물의 꼭대기보다 높아야 합니다. 모든 건물에 대해 볼 수 있는 건물의 최대 개수를 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[51]; // 건물의 높이를 저장하는 배열
int cnt[51]; // 각 건물에서 보이는 건물의 수를 저장하는 배열

// 직선이 다른 건물 꼭대기를 통과하는지 확인하는 함수
int checkLineMeetF(double x1, double y1, double x2, double y2, double x, double y) {
    // 직선의 기울기와 y절편을 구함
    double slope = (y1 - y2) / (x1 - x2);
    double intercept = y1 - slope * x1;

    // 직선 위의 y값과 건물 높이를 비교
    if (slope * x + intercept < y) {
        return 1; // 보이는 경우
    }
    return 0; // 보이지 않는 경우
}

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

    int n;
    cin >> n;

    // 건물 높이 입력
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    // 모든 건물 쌍에 대해 보이는지 확인
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int check = 1;
            for (int t = i + 1; t < j; t++) {
                if (checkLineMeetF(i, arr[i], j, arr[j], t, arr[t]) == 0) {
                    check = 0; // 직선이 건물에 가려짐
                    break;
                }
            }
            if (check == 1) {
                cnt[i]++;
                cnt[j]++;
            }
        }
    }

    // 가장 많이 보이는 건물의 수를 찾음
    int maxAns = 0;
    for (int i = 1; i <= n; i++) {
        maxAns = max(maxAns, cnt[i]);
    }

    // 결과 출력
    cout << maxAns;
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 직선 기울기와 y절편 계산: - 두 건물 (x1, y1)와 (x2, y2)를 연결하는 직선의 방정식을 계산합니다.
• 가시성 검사: - 직선 위의 y값과 중간 건물의 높이를 비교하여, 중간 건물 꼭대기보다 직선이 높으면 "보인다"고 판단합니다.
• 건물 쌍 확인: - 모든 건물 쌍에 대해 중간에 있는 건물이 가리는지 확인하고, 보이는 경우 두 건물의 cnt를 증가시킵니다.

시간 복잡도 분석

• **이중 반복문:** 건물의 쌍을 모두 확인하므로 **O(n²)**입니다.
• **가시성 검사:** 한 쌍에 대해 중간 건물을 확인하는데 최대 **O(n)** 시간이 소요됩니다.
• 총 시간 복잡도: **O(n³)**입니다. 최대 n = 50이므로 충분히 수행 가능합니다.

---

결과

모든 건물에서 볼 수 있는 건물의 최대 개수를 출력합니다.

• 입력 예시:

  5  
  1 5 3 2 4

• 출력 예시:

  2

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!