백준 1027 고층 건물 (c++) : 피너클

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

1027번: 고층 건물

수학문제다.

대충 위와 같이 빌딩들이 있다고 가정하자. 선분으로 하니 잘 안보여서 그냥 도형으로 했다.

첫번째 건물에서 두번째 건물은 당연히 보인다. 세 번째 건물은 당연히 보이지 않는걸 알수있다.

그렇다면 이걸 코드로 어떻게 작성해야할까.

각 선분의 기울기를 확인하면 된다. 이전 건물까지의 기울기보다 이번 건물의 기울기가 작다면

이번 건물은 보이지 않는다. 반대로 더 크다면 이번 건물은 보이게 된다.

위 처럼 말이다. 그렇다면 내려다 보는건 어떻게 해야할까?

똑같이 하면 된다. 이전 건물의 기울기 보다만 높으면 무조건 보인다.

여기서 중요한건 두 건물에서 동시에 보인다는 것이다. 4번째 건물에서 7번째 건물이 보인다면

7번째 건물에서도 4번째 건물이 보인다는 뜻이다.

int n;
int arr[51];
int inCount[51];

사용할 변수다.

inCount는 각 건물에서 다른 건물이 얼마나 보이는지를 나타낸다.

inCount[1] = 5라면 1번건물에서 5개의 건물이 보이는것이다.

cin >> n;
for (int i = 1; i <= n; i++) {
    cin >> arr[i];
    inCount[i] = 0;
}
for (int i = 1; i <= n; i++) {
    solve(i, i + 1, -1000000000);
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, inCount[i]);
cout << ans << endl;

메인함수에서는

값을 입력받으며 inCount를 초기화하고 모든 부분에서 solve함수를 돌린 뒤

ans에 inCount중 가장 높은 값을 저장하고 출력하면 된다.

void solve(int first, int idx, double last) {
	if (idx == n + 1) return;
	double now = (double)(arr[idx] - arr[first]) / (idx - first);
	if (now <= last) {
		solve(first, idx + 1, last);
		return;
	}
	inCount[first]++;
	inCount[idx]++;
	solve(first, idx + 1, now);
}

solve함수는 (처음 시작 건물, 현재 건물, 이전 건물의 기울기)를 전달받는다.

만약 현재 건물의 인덱스가 n+1이라면 범위를 벗어난것이니 그대로 함수를 종료한다.

now에는 시작 건물과 현재 건물의 기울기가 들어간다.

만약 이전 건물의 기울기가 현재 건물의 기울기보다 크다면 현재 건물을 볼수 없는 것이다.

idx만 +1하고 함수를 종료한다.

기울기가 이전 건물보다 더 크다면 볼수 있다는 뜻이다.

양쪽 건물의 inCount에 1을 더하고 idx와 now를 업데이트해 solve함수를 돌리면 된다.

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int arr[51];
int inCount[51];

void solve(int first, int idx, double last) {
	if (idx == n + 1) return;
	double now = (double)(arr[idx] - arr[first]) / (idx - first);
	if (now <= last) {
		solve(first, idx + 1, last);
		return;
	}
	inCount[first]++;
	inCount[idx]++;
	solve(first, idx + 1, now);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		inCount[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		solve(i, i + 1, -1000000000);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) ans = max(ans, inCount[i]);
	cout << ans << endl;
}

전체코드다.