[BOJ] 백준 1027 고층건물 c++ (브루트포스, 기하학)

문제 출처 : https://www.acmicpc.net/problem/1027

1027번: 고층 건물

---

풀이

고층 빌딩 리스트가 주어지는데, 가장 많은 빌딩이 보이는 수를 출력하는 문제이다.

이때 A에서 B빌딩이 보이려면 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다.

 

처음에 두 선분을 구하고 사이에 있는 빌딩의 높이가 그 선분을 건드리는지 확인해봐야하나 고민했지만, 결론은 기울기였다.

2중 for문을 돌며 모든 빌딩과 다른 빌딩을 확인해 해당 빌딩과 기준 빌딩의 기울기가 최고 기울기보다 크면 보이는 경우로 판단한다.

---

기울기 계산

y 증가량을 x증가량으로 나눈 공식을 쓰면 된다.

building 배열은 높이를 저장하고 기준 빌딩이 i, 확인할 빌딩이 j라고 했을때 공식은 아래와 같다.

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

 

2중 for문 돌며 확인 및 최고 기울기 갱신

초기 기울기는 최소값으로 놓고, 2중 for문을 돌며 기울기를 확인한다.

해당 기울기가 최고 기울기보다 크면 두 빌딩에 보이는 빌딩 수를 1 증가시키고, 최고 기울기를 갱신한다.

// building[] : 빌딩 높이
// cnt[] : 보이는 빌딩 수
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;
        }
    }
}

---

코드

#include <bits/stdc++.h>

using namespace std;

int res;

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

	int N;
	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(auto elem : cnt)
		res = max(res, elem);
	cout << res << '\n';
	return 0;
}