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

문제링크 : https://www.acmicpc.net/problem/1027

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;
int arr[51];
int cnt[51];

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

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

    for(int i=0; i<N-1; i++)
    {
        double maxV = -INT_MAX;
        for(int j=i+1; j<N; j++)
        {
            double tmp = (double)(arr[j]-arr[i])/(j-i);
            if(tmp > maxV)
            {
                cnt[i]++;
                cnt[j]++;
                maxV = tmp;
            }
        }
    }

    cout << *max_element(cnt, cnt+N);

    return 0;
}

 

기울기를 활용한 문제다.

입력받은 모든 빌딩의 거리와 높이차를 기준으로 기울기를 계산하며, 가장 큰 키울기일 때의 가능한 수를 체크한다.

카운팅의 경우 최대 기울기 갱신 때마다 양쪽 빌딩을 모두 카운터 해주며, 가장 큰 기울기 일때 누적된 가장 큰 값을 출력하게 된다.