[C++]백준 1027번 : 고층건물

www.acmicpc.net/problem/1027

1027번: 고층 건물

1. 접근

기울기에 따라 옥상이 보이는지 확인할 수 있다.

 

2. 틀린 이유, 보완점

최대 높이가 1000000000000인 것에 따라 초기 각도 변수 값을 적절하게 초기화해주어야한다.

아니면 -DBL_MAX로 초기화해도 좋다.

 

추가로 선택한 건물에서 양 옆을 매번 확인할 필요없이 

i->j 옥상이 보이면 j->i 옥상이 보이는 것을 이용하여 2차원 배열 check를 통해 연산을 최소화하자.

 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#include <cfloat>

using namespace std;

int N, ans = 0, h[50];
bool check[50][50];
const double INF = -1.0 * 1000000001;

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> h[i];

	for (int i = 0; i < N; i++){
		int cnt = 0;
		double mArc = INF;

		for (int j = i + 1; j < N; j++){
			double cArc = 1.0 * (h[j] - h[i]) / (j - i);
			if (mArc < cArc){
				cnt++;
				mArc = cArc;
				check[i][j] = true;
			}
		}

		for (int j = 0; j < i; j++){
			if (check[j][i])
				cnt++;
		}

		if (ans < cnt)
			ans = cnt;
	}

	cout << ans;


	return 0;
}