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

 

 

<코드>

#include<iostream>
#include<algorithm>
using namespace std;

int N;
double building[51];
int x, ans, cnt;
double gradient, memo;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

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

		memo = 1000000000; // 10억
		// 왼쪽 빌딩 탐색
		for (int j = i - 1; j >= 1; j--)
		{
			gradient = (building[i] - building[j]) / ((double)i - (double)j);
			if (gradient < memo)
			{
				cnt++;
				memo = gradient;
			}
		}

		memo = -1000000000; // -10억
		// 오른쪽 빌딩 탐색
		for (int j = i + 1; j <= N; j++)
		{
			gradient = (building[j] - building[i]) / ((double)j - (double)i);
			if (gradient > memo)
			{
				cnt++;
				memo = gradient;
			}
		}
		ans = max(ans, cnt);

	}

	cout << ans;
}

 

풀이 방법

 

i번째 빌딩 기준으로 왼쪽을 살펴볼때는 기울기가 감소하는 순서로,

오른쪽을 살펴볼때는 기울기가 증가하는 순서로 빌딩을 카운트 한다.

 

 

www.acmicpc.net/problem/1027

1027번: 고층 건물