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

문제 링크

1027번: 고층 건물

 

풀이 )

  idx번째 건물에 대해서

• 왼쪽에 있는 건물은 idx-1부터 0까지 기울기가 감소하면 반환값을 1씩 늘리고, 기울기를 갱신한다.
• 오른쪽에 있는 건물은 idx+1부터 n까지 기울기가 증가하면 반환값을 1씩 늘리고, 기울기를 갱신한다.

 

  0번 건물은 왼쪽에 건물이 없기 때문에 오른쪽 건물에 대해서만 숫자를 세고

  n-1번 건물은 오른쪽에 건물이 없기 때문에 왼쪽 건물에 대해서만 숫자를 센다.

 

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

using namespace std;

int left(vector<int> v, int idx){
    int ret = 0;
    double m = 1e9;
    for(int i = idx-1; i >= 0; --i){
        if((double)(v[i]-v[idx])/(i-idx) >= m)
            continue;

        m = (double)(v[i]-v[idx])/(i-idx);
        ret++;
    }

    return ret;
}

int right(vector<int> v, int idx){
    int ret = 0, n = v.size();
    double m = -1e9;
    for(int i = idx+1; i < n; ++i){
        if((double)(v[i]-v[idx])/(i-idx) <= m)
            continue;

        m = (double)(v[i]-v[idx])/(i-idx);
        ret++;
    }

    return ret;
}

int main(void){
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i)
        cin >> v[i];

    int ans = right(v, 0);
    for(int i = 1; i < n-1; ++i)
        ans = max(ans, left(v, i)+right(v, i));
    ans = max(ans, left(v, n-1));

    cout << ans << '\n';
}