[백준알고리즘] 1027번: 고층 건물 -C++

[백준알고리즘] 1027번: 고층 건물 -C++

1027번: 고층 건물 (acmicpc.net)

1027번: 고층 건물

Gold IV 단계의 난이도인데 생각보다 쉬웠던 것 같다.

 

문제 자체도 크게 어렵지 않은 것 같고.. 논리적으로도 명확하게 주제를 준 것 같다. 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

문제의 요구 사항부터 살펴보도록 하겠다.

1. 선분으로 나타낼 수 있는 빌딩들이 존재한다.
2. 각 빌딩의 지붕에서 다른 빌딩의 지붕으로 선분을 그린다.
3. 다른 빌딩의 지붕과의 선분 사이에 다른 어떤 건물도 존재하지 않는 경우, 해당 빌딩을 '보이는 빌딩'이라고 생ㄱ가한다.
4. 이러한 '보이는 빌딩'이 가장 많은 빌딩에서 '보이는 빌딩'의 수를 구하라.

 

나머지는 크게 어렵지 않겠지만, 이탤릭체로 기울인 "선분"이라는 조건만 고려하면 아마 헤매는 구간도 없지 않을까 싶다. 즉, 한 점이 고정된 상태에서 "선분" 사이에 다른 "선분"이 겹치는 경우를 제외하라는 의미다. (기울기가 같은 선분)

 

문제 자체를 푸는 것은 어렵지 않았다. 주어진 범위와 시간 제한을 통해 충분히 \( O ( N^2 ) \)의 시간복잡도로도 충분히 통과할 수 있을 것이라고 생각했다.

 

문제를 풀 때에는 \(0\)번 빌딩부터(문제에서는 \(1\)부터라고는 했지만) \( n - 1 \)까지 인덱싱 하면서 기준 빌딩을 잡는다. 그리고 각 기준 빌딩에서 오른쪽 방향으로 '보이는 빌딩'의 개수를 세준다. 이때 '보이는 빌딩'이 되려면, 기준 빌딩에서 이전 '보이는 빌딩'과 이어진 "선분"의 기울기보다 커야 한다.

 

 

3가지 예를 들어서 다음의 경우를 살펴보겠다.

 

먼저, 건물의 높이가 다음과 같다고 생각해보자.

0 번	1 번	2 번
4	1	2

 

그렇다면, 0번 건물의 지붕에서 1번 건물의 지붕까지의 기울기는 \( -3 / 1 \)이 될 것이다. 그리고 이 경우가 현재는 '보이는 건물' 중 가장 기울기가 큰 값이 된다. 따라서, 0번 건물과 1번 건물은 서로 보이기 때문에 각각의 보이는 건물의 수와 1번 건물에서 보이는 건물의 수를 1씩 증가시켜준다.

마찬가지로 0번 건물의 지붕에서 2번 건물의 지붕까지의 기울기는 \( -2 / 2 \)가 될 것이다. 이 값은 0번 건물의 지붕과 1번 건물의 지붕을 잇는 선분의 기울기보다 크다. ( \( -3 < -1 \) )

따라서, 0번에서 보이는 건물의 수는 또다시 1 증가해 2가 되며, 2번 건물의 보이는 건물 수도 1 증가한다.

 

다음으로, 건물의 높이가 다음과 같다고 생각해보자.

0 번	1 번	2 번
4	3	1

 

이 경우에도 위의 예시와 마찬가지로 접근해 보겠다. 

0번 건물의 지붕에서 1번 건물의 지붕까지의 선분을 잇는다면, 기울기는 \( -1 / 1 = -1 \)가 될 것이다.

마찬가지로, 0번 건물의 지붕에서 2번 건물의 지붕까지의 선분을 잇는다면, 기울기는 \( -3 / 2 = -1.5 \)가 될 것이다.

이때 0번 건물에서 1번 건물까지의 선분의 기울기가 -1로, -1이 '보이는 건물'과의 최대 기울기였다. 그런데, 0번 건물에서 2번 건물까지의 선분의 기울기가 -1.5로 기존 보이던 건물(1번 건물)의 최대 기울기보다 작은 기울기를 갖기 때문에 이 경우에는 '보이는 건물'로 추가될 수 없다.

따라서, 0번 건물의 보이는 건물의 수는 1이다.

 

마지막으로, 건물의 높이가 다음과 같다고 생각해보자.

0 번	1 번	2 번
4	3	2

 

 

이번에도 마찬가지로 살펴보겠다.

0번 건물의 지붕에서 1번 건물의 지붕까지 잇는 선분의 기울기는 \( -1 / 1 = -1 \)이다.

또한, 0번 건물의 지붕에서 2번 건물의 지붕까지 잇는 선분의 기울기는 \( -2 / 2 = 1 \)이다.

기존 보이던 건물인 1번 건물까지의 기울기와 동일하게 되는데, 이때도 마찬가지로 기존 보이던 건물과의 기울기보다 크지 않기 때문에 0번 건물의 보이는 건물의 수는 증가하지 않는다.

실제로 그림을 그린다고 하더라도 2번 건물은 1번 건물에 가려져서 안보이는 것과 마찬가지이기 때문이다.

 

---

 

아래는 최종적으로 구현한 C++ 코드다. vector 안의 최대 원소를 구하기 위해 <algorithm> 헤더의 max_element를 사용했다. max_element의 경우에는 포인터값으로 return 하기 때문에 *를 반드시 앞에 붙여야 한다.

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

void solve(void);

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

	solve();
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<int> buildings;
	for (int i = 0; i < n; i++)
	{
		int temp;
		std::cin >> temp;

		buildings.push_back(temp);
	}

	std::vector<int> count(n);
	for (int i = 0; i < n; i++)
	{
		double maxGradient = -1000000000;

		for (int j = i + 1; j < n; j++)
		{
			int h = buildings[j] - buildings[i];
			int w = j - i;
			double g = h * 1.0 / w;

			if (g <= maxGradient)
				continue;

			maxGradient = g;
			count[i]++; count[j]++;
		}
	}
	
	std::cout << *max_element(count.begin(), count.end());
}