백준_1027_고층건물(브루트포스 알고리즘)

[youbeen2798]

문제 링크 : https://www.acmicpc.net/problem/1027
문제 번호 : 1027
문제 난이도 : 골드4

문제 내용

• 빌딩은 총 N개로, N개의 건물의 높이가 주어짐
• 각 건물마다 볼 수 있는 건물들의 개수를 구해, 가장 많은 건물을 구하고, 거기서 보이는 빌딩의 수를 출력 (다른 건물을 접해서도 안됨)

이용한 알고리즘

• 브루트 포스 알고리즘( 하나씩 접근하니까....(?))

접근 방법

• 각 건물마다 오른쪽부터 시작해 기울기(건물의 높이 차이 / 건물의 거리)를 구하고, 기울기의 최대값이 갱신될 때마다 두 건물의 보이는 건물의 개수를 1 증가 시켜줌

풀이 코드

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

using namespace std;

int n;

int building[51]; //각 빌딩의 높이

int main() {
	ios_base::sync_with_stdio(0); //입출력 빠르게
	cin.tie(0);
	cout.tie(0);

	cin >> n; //건물의 개수

	vector <int> cnt(n); //각 건물에서 보이는 건물의 개수

	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		building[i] = k; //각 빌딩의 높이
	}


	for (int i = 0; i < n; i++) {
		double mini = -1000000001; //문제 조건으로 봤을 때 기울기의 최소값

		for (int j = i + 1; j < n; j++) {
			int height = building[j] - building[i];
			int width = j - i;
			double k = height * 1.0 / width; //건물과 건물 사이의 기울기

			if (k > mini) {
				mini = k; //기울기 값 갱신
				cnt[i]++; 
				cnt[j]++;
			}
		}
	}

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

문제 포인트

• '기울기'의 최댓값만 갱신하면 되는 문제로, 아이디어 싸움인 문제인것 같다.
• 나는.. 기울기를 이용하려한 접근법은 맞았지만, 각 건물의 왼쪽과 오른쪽을 나누어 각각 카운트를 하려하니 좀 해메이게 되었음ㅠㅠ
• 다시 생각해보니, 그냥 해당 건물의 오른쪽 건물들만 확인하고, 두 건물의 카운트를 한꺼번에 올리면 됨!!
• 이런건,, 문제를 많이 풀다보면 그냥 익숙해지겠지..(하하)

기억해야 할 점

• max_element 함수 기억하기!! ( <= header는 이고, 각 배열혹은 벡터의 최대원소값을 가져올 수 있는 함수임 )
• 반대로, min_element 함수도 있음ㅎㅎ