[c++] sw expert academy - 1일차 view1

브루트포스로 풀면 됩니다.

2번째에 위치한 첫번째 건물부터 n-2 번째 위치한 끝 건물까지 돌면서

현재 위치를 k 라 한다면 k-2, k-1, k+1, k+2 위치에 건물들과 차이를 비교해서

0 또는 음수가 나온다면 ( 더 높은 건물이 있음) 다음 위치로 continue.

0 또는 음수가 없다면 차이들 중 가장 작은 값을 고르면 k건물의 조망권이 확보된 세대 수가 나옵니다.

 

시간복잡도는 O(t*n) 입니다.

 

n1,n2,n3,n4 = 건물들과의 차이

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

int main()
{
    int n,k,n1,n2,n3,n4;
    int t=10;
    while(t--){
        cin>>n;
        vector<int> v(1001,0);
        for(int i=0;i<n;i++){
            cin>>k;
            v[i]=k;
        }   
        
        int val = 0;
        for(int i=2;i<n-2;i++){
            n1 = v[i]-v[i-2];
            n2 = v[i]-v[i-1];
            n3 = v[i]-v[i+1];
            n4 = v[i]-v[i+2];
            if(n1 <= 0 || n2 <= 0 || n3 <= 0 || n4 <= 0){
                continue;
            }
            val += min({n1, n2, n3, n4});
        }
        
        cout << "#" << 10-t << " " << val << "\n";
    }
    
    return 0;
}