[백준] 1027번 고층 건물 - C++ (Bruteforce)

문제요약

문제에서 N과 N개만큼의 건물 높이가 주어진다. i번째 빌딩은 (i, 0) 부터 (i, 높이) 까지의 선분으로 나타낸다. 이 때 건물 A에서 건물 B를 볼 수 있으려면, 그 사이에 A-B를 잇는 선분에 닿는 건물이 없으면 된다. 

빌딩에서 보이는 건물 수의 최댓값을 출력하면 된다.

 

풀이방법

1. 건물의 기울기를 계산해 비교하는 방식으로 문제를 해결하고자 했다. 

 

2. 건물 A를 기준으로 for문을 이용해 A 오른쪽에 있는 모든 건물의 기울기를 계산해나가며 최댓값을 갱신한다. (초기 최댓값은 문제에서 가능한 범위보다 작게 설정한다.)

 

3. 건물 A에서 B가 보이는지를 판단하고자 할 때, 현재 최댓값은 A에서 B-1까지의 건물을 이은 선분 기울기의 최댓값이다. 이 값보다 A-B 선분의 기울기가 크다면, A-B를 이은 선분에 A에서 B-1까지의 어떤 건물도 접하지 않는 것이므로 A에서 B를, B에서 A를 볼 수 있는 것으로 판단한다. 그리고 최댓값을 갱신해 준다.

 

4. 탐색할 때 두 건물 모두의 answer index에 값을 더해주고 (서로 볼 수 있는 것이므로), 해당 건물을 기준으로 탐색할 때 그 건물의 오른쪽에 있는 건물만 탐색하도록 한다.

 

5. 탐색이 끝난 뒤 answer index를 정렬하는 방식으로 최댓값을 구한다. 

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main (){
	int N;
	cin >> N;
	int arr[N+1];
	for(int i=1; i<=N; i++){
		cin >> arr[i]; 
	} // 건물의 높이 array에 저장하기. 건물 번호가 1~N이므로 1~N에 저장 
	
	int ans[N+1] = {0,}; // 각 건물에서 보이는 건물 개수를 저장할 배열  
	for(int i=1; i<=N; i++){
		double maxx = -9999999999;
		for(int j=i+1; j<=N; j++){ //건물 i를 기준으로 오른쪽 건물 탐색 
			double level = double(arr[j]-arr[i]) / (j-i); // 기울기 구하기 
			if (level > maxx) { // 현재 최댓값보다 기울기가 크면 보이는 건물로 판단 
				ans[i]++; 
				ans[j]++; // 양 건물 모두에서 값 더해주기 
				maxx = level; 
			}
		}
	}
	sort(ans+1, ans+N+1); // 1부터 N까지의 값을 sort 
	cout << ans[N]; // 최댓값 출력 
}

후기

이중 for문을 이용해 탐색 자체는 어렵지 않았지만 두 건물이 보이는 건물인지를 판단하는 알고리즘을 생각하는 것이 쉽지 않았던 것 같다.