백준 1027 c++ "고층 건물" -PlusUltraCode-

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

[필자 사고]

기하학 문제 즉 기울기를 이용하여 문제를 해결해야 하는 것이다.

특정 위치에서 건물이 보이는 원리는 기울기로 판단이 가능하다. 기울기가 작은-> 큰 쪽으로 갈수록 보이고 
만약 기울기가 큰-> 작 이면 이후 건물들은 볼 수 없다. 

즉 브루토포스 2중포문을 이용하여 모든 기울기들을 구하고 각 위치에 맞게 cnt값을 증가시켜 주면 된다.

필자는 2중포문을 이용하여 특정 위치에서 i라는 건물에서 다른 건물들의 기울기를 구했따. 

한쪽이 볼 수 있으면 다른 쪽도 볼 수 있다는 원리르 이용 했다. 

 

아래는 자세한 코드 해설이다.

[코드 해설]

main()

• 프로그램의 시작점이다.
• 건물 개수 N을 입력받는다.
• 건물 높이를 저장할 벡터 arr와 각 건물이 볼 수 있는 건물 수를 저장할 벡터 cnt를 크기 N+1로 초기화한다.
• 반복문을 통해 1번부터 N번까지 건물 높이를 입력받는다.

---

for (int i = 1; i <= N; i++)

• i번째 건물을 기준으로 오른쪽 건물들을 검사한다.
• 기준 건물 i에서 새로 시작할 때마다 maxLine을 INT_MIN으로 초기화한다.
• 이 값은 i에서 본 오른쪽 건물들과의 직선 기울기 중 현재까지 가장 큰 값을 저장하는 역할을 한다.

---

for (int k = i + 1; k <= N; k++)

• i보다 오른쪽에 있는 건물 k를 하나씩 확인한다.
• 두 건물 i와 k를 잇는 직선의 기울기 line을 계산한다.
  공식: (arr[i] - arr[k]) / (i - k)
• 이 기울기 값이 maxLine보다 크다면, i와 k는 서로 볼 수 있다고 판정한다.

---

if (line > maxLine)

• 조건이 참이면,
  • cnt[i]++와 cnt[k]++를 통해 두 건물이 서로를 볼 수 있는 횟수를 증가시킨다.
  • maxLine = line으로 갱신해 현재까지 가장 큰 기울기를 저장한다.

---

cout << *max_element(cnt.begin(), cnt.end());

• 모든 계산이 끝난 뒤, cnt 벡터에서 최댓값을 찾아 출력한다.
• 즉, 가장 많은 건물을 볼 수 있는 건물이 몇 개를 볼 수 있는지 출력한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std;

int N;
vector<int> arr;
vector<int> cnt;
int main(void) {
	cin >> N;
	arr.assign(N + 1, 0);
	cnt.assign(N + 1, 0);
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}


	for (int i = 1; i <= N; i++) {

		double maxLine = INT_MIN;
		for (int k = i + 1; k <= N; k++) {
			double line = (double)(arr[i] - arr[k]) / (i - k);

			if (line > maxLine) {
				cnt[i]++;
				cnt[k]++;
				maxLine = line;
			}
		}
	}
	cout << *max_element(cnt.begin(), cnt.end());
}