1027번: 고층 건물

문제 설명

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

1027번: 고층 건물

[문제]

 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

 

[입력]

 첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

 

[출력]

 첫째 줄에 문제의 정답을 출력한다.

 

[예제 입력 1]

15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5

[예제 출력 1]

7

---

풀이

 해당 문제에선 빌딩이 최대 50개 정도이기 때문에 일일히 직접 비교를 해도 시간 초과의 위험은 존재하지 않는다. 게다가 문제에서 언급되는 설명인 볼 수 있는 빌딩이 되려면 해당 두 지붕을 잇는 선분에 다른 고층 빌딩이 지나가거나 접하지 않아야 한다 하는데, 이는 결국 기울기라는 개념으로 대체 가능하다. 배열 상 인덱스 차이를 x축, 빌딩의 높이를 y축이라 생각하고 이를 기울기를 구하는 데 적용 가능하기 때문에, 각 중심 빌딩을 기준으로 양 쪽으로 하나씩 진행하며 앞선 가장 기울기가 높았던 빌딩과 현재 빌딩에 대한 기울기를 비교하여 현재 빌딩이 높다면 개수를 하나 추가하고 최고 기울기를 최신화하는 방법으로 코드를 작성했다.

 추가적으로 기울기라는 계산이 정수가 아닌 수로 나올 확률이 매우 높기 때문에 자료형으로 인한 계산 오차가 생길 수 있어, 이를 단순히 곱하기를 통한 비교로 바꾸어 작성했다.

#include <iostream>

using namespace std;

long long building[50]; //빌딩 높이
int N; //건물 개수

int search(int index) {
	long long maxDis, maxHeight;
	long long dis, height;
	int result = 0;

	if (index > 0) {//좌측 빌딩이 있는 경우
		maxDis = 1;
		maxHeight = building[index - 1] - building[index];

		++result;

		for (int i = index - 1; i >= 0; i--) {//값을 비교해 더 크면 개수+1, 최대 기울기 최신화
			dis = (long long)index - i;
			height = building[i] - building[index];

			if (height * maxDis > maxHeight * dis) {
				++result;
				maxDis = dis;
				maxHeight = height;
			}
		}
	}

	if (index < N - 1) {//우측 빌딩이 있는 경우
		maxDis = 1;
		maxHeight = building[index + 1] - building[index];

		++result;

		for (int i = index + 1; i < N; i++) {//값을 비교해 더 크면 개수+1, 최대 기울기 최신화
			dis = (long long)i - index;
			height = building[i] - building[index];

			if (height * maxDis > maxHeight * dis) {
				++result;
				maxDis = dis;
				maxHeight = height;
			}
		}
	}

	return result;
}

int main() {
	long long height;
	int answer = 0;

	cin >> N;

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

	for (int i = 0; i < N; i++)
		answer = max(answer, search(i));

	cout << answer;

	return 0;
}

---

결과