[BOJ/C++] 1027 고층 건물

문제

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

풀이

💡빌딩이 서로 보이는지 알아보려면 기울기를 이용해야 한다. 해당 빌딩과 기준 빌딩의 기울기가 최고 기울기보다 크면 보이는 경우임

• 기울기 계산

double level = (double)(building[j] - building[i]) / (j - i);

• 2중 for문 돌며 기울기 갱신

  • 초기 기울기는 최소값으로 놓고, 2중 for문 돌며 기울기 확인
  • 해당 기울기가 최고 기울기보다 크면 두 빌딩에 보이는 빌딩 수를 1 증가시키고, 최고 기울기 갱신

• cnt 배열에서 보이는 건물 수를 확인하고, 최댓값을 구한다.
  
  

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


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

	int N;
	int ans = 0;
	cin >> N;

	vector<int> building(N);
	vector<int> cnt(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> building[i];
	}

	for (int i = 0; i < N; i++) {
		double max_level = -9999999999;
		for (int j = i + 1; j < N; j++) {
			double level = (double)(building[j] - building[i]) / (j - i);
			if (level > max_level) {
				cnt[i]++;
				cnt[j]++;
				max_level = level;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		ans = max(ans, cnt[i]);
	}

	cout << ans;

	return 0;
}