[BOJ] 1027 고층 건물

문제 링크

 

www.acmicpc.net/problem/1027

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

고층 건물 A에서 왼쪽, 오른쪽으로 건물들을 보면서 기울기와 최대 높이를 측정하고, 이를 통해 이 건물에서 최대 몇 개의 다른 건물을 볼 수 있는지 구한다. 먼저 왼쪽으로 보면서 그리고 건물 B가 건물 A보다 높은지, 낮은지에 따라 처리를 해주고, 그 다음 오른쪽으로 보면서 건물 B가 건물 A보다 높은지, 낮은지에 따라 처리를 해준다. 기울기는 (A의 높이 - B의 높이) / (A 좌표 - B 좌표)로 구할 수 있다.

 

왼쪽으로 볼 때와 오른쪽으로 볼 때 각각 maxHeight에 지금까지 본 건물들 중 가장 높은 건물의 높이를 저장해둔다. 다음에 볼 건물의 높이가 maxHeight보다 낮고, maxHeight가 건물 A의 높이보다 크다면 그 건물은 A에서 볼 수 없으므로 패스한다.

 

자세한 과정은 아래와 같다.

---

먼저 tmpPos=INF, tmpNeg=-INF, maxHeight=0으로 초기화해준다.

 

  1. 왼쪽으로 보는 경우

     1-1. 건물 B의 높이가 A 이상인 경우 - 이때 A를 기준으로 한 기울기는 양수이며, tmpNeg에 저장되어있는 값보다 기

                                                      울기가 작다면 A에서 B를 볼 수 있으므로 카운터를 하나 올려주고, tmpNeg에

                                                      현재의 기울기를 저장한다. 

 

     1-2. 건물 B의 높이가 A 미만인 경우 - 이때 A를 기준으로 한 기울기는 음수이며, tmpPos에 저장되어있는 값보다 기

                                                      울기의 절댓값이 크다면 A에서 B를 볼 수 있으므로 카운터를 하나 올려주고,                                                        tmpPos에 현재의 기울기를 저장한다.

          

  왼쪽으로 보는 과정이 끝나면 다시 tmpPos=INF, tmpNeg=-INF, maxHeight=0으로 초기화해준다.

 

  2. 오른쪽으로 보는 경우

     1-1. 건물 B의 높이가 A 이상인 경우 - 이때 A를 기준으로 한 기울기는 양수이며, tmpPos에 저장되어있는 값보다 기

                                                      울기가 크다면 A에서 B를 볼 수 있으므로 카운터를 하나 올려주고, tmpPos에 

                                                      현재의 기울기를 저장한다. 

 

     1-2. 건물 B의 높이가 A 미만인 경우 - 이때 A를 기준으로 한 기울기는 음수이며, tmpNeg에 저장되어있는 값보다 기

                                                      울기의 절댓값이 작다면 A에서 B를 볼 수 있으므로 카운터를 하나 올려주고,                                                        tmpNeg에 현재의 기울기를 저장한다.

---

이를 구현하면 아래와 같이 나타낼 수 있다.

#include <iostream>
using namespace std;

const int INF=1e9;
int main() {
	int i, j, n, arr[50];
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int ret = -1;
	for (i = 0; i < n; i++) {
		int val = arr[i], cnt=0, maxHeight=0;
		double tmpNeg=INF, tmpPos=-INF;
		for (j = i-1; j >= 0; j--) {
			if(maxHeight >= arr[i] && maxHeight>=arr[j]) continue;
			if(maxHeight<arr[j]) maxHeight=arr[j];
			double slope=(double)(arr[j] - arr[i]) / (j - i);
			if(slope<0){ // 건물 i가 건물 j보다 더 높은 경우
				if(-slope>tmpPos){// slope가 현재 최대 기울기보다 크다면, 이 빌딩은 다른 빌딩에 가려지지 않는다.
					tmpPos=-slope;
					cnt++;
				}
			}
			else{ //건물 i보다 건물 j가 더 높은 경우
				if(slope<tmpNeg){// slope가 현재 최대 기울기보다 작다면, 이 빌딩은 다른 빌딩에 가려지지 않는다.
					tmpNeg=slope;
					cnt++;
				}
			}
		}
		tmpNeg=INF, tmpPos=-INF, maxHeight=0;
		for (j = i + 1; j < n; j++) {
			if(maxHeight >= arr[i] && maxHeight>=arr[j]) continue;
			if(maxHeight<arr[j]) maxHeight=arr[j];
			double slope=(double)(arr[j] - arr[i]) / (j - i);
			if(slope>=0){ // 건물 i가 건물 j보다 더 높은 경우
				if(slope>tmpPos){// slope가 현재 최대 기울기보다 크다면, 이 빌딩은 다른 빌딩에 가려지지 않는다.
					tmpPos=slope;
					cnt++;
				}
			}
			else{ //건물 i보다 건물 j가 더 높은 경우
				if(-slope<tmpNeg){// slope가 현재 최대 기울기보다 작다면, 이 빌딩은 다른 빌딩에 가려지지 않는다.
					tmpNeg=-slope;
					cnt++;
				}
			}
		}
		if(ret<cnt) ret=cnt;
	}
	cout<<ret;

}