[백준 1027] 고층 건물 (C#, C++) - soo:bak

문제 링크

1027번 - 고층 건물

설명

각 빌딩은 좌표의 세로선분으로 표현됩니다. 빌딩 A에서 빌딩 B가 보이려면 두 지붕을 잇는 직선이 사이의 다른 빌딩을 지나거나 접하지 않아야 합니다.

즉, A 기준으로 해당 방향에서 지금까지 본 빌딩들보다 더 큰 기울기를 가져야 합니다. 모든 빌딩에 대해 보이는 빌딩 수를 세고, 그중 최대를 출력하는 문제입니다.

접근법

먼저, 각 빌딩에서 오른쪽 방향만 순회합니다. 최대 기울기를 매우 작은 값으로 두고, 오른쪽 빌딩들의 기울기를 계산합니다.

다음으로, 기울기가 최대 기울기보다 크면 두 빌딩이 서로 보이는 것이므로 양쪽 빌딩의 보이는 수를 모두 증가시킵니다. 이렇게 하면 왼쪽 방향을 따로 처리하지 않아도 됩니다.

이후, 모든 빌딩의 보이는 수 중 최댓값을 출력합니다. 기울기는 실수이므로 실수 자료형으로 계산합니다.

---

Code

C#

using System;
using System.Linq;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var parts = Console.ReadLine()!.Split();
      var buildings = new int[n + 1];
      var cntView = new int[n + 1];

      for (var i = 1; i <= n; i++)
        buildings[i] = int.Parse(parts[i - 1]);

      for (var cur = 1; cur <= n; cur++) {
        var maxSlope = -1e9;
        for (var i = cur + 1; i <= n; i++) {
          var view = (double)(buildings[i] - buildings[cur]) / (i - cur);
          if (view > maxSlope) {
            cntView[cur]++;
            cntView[i]++;
            maxSlope = view;
          }
        }
      }

      Console.WriteLine(cntView.Max());
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

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

  int n; cin >> n;
  vi buildings(n + 1), cntView(n + 1, 0);
  for (int i = 1; i <= n; i++)
    cin >> buildings[i];

  for (int cur = 1; cur <= n; cur++) {
    double maxSlope = -1e9;
    for (int i = cur + 1; i <= n; i++) {
      double view = (double)(buildings[i] - buildings[cur]) / (i - cur);
      if (view > maxSlope) {
        cntView[cur]++;
        cntView[i]++;
        maxSlope = view;
      }
    }
  }

  sort(cntView.rbegin(), cntView.rend());
  cout << cntView[0] << "\n";

  return 0;
}