← 전체 글로 돌아가기
competitive-programming2021년 1월 17일1분 분량

[Codeforces] 1467B. Hills And Valleys 풀이

수정일: 2021년 3월 16일

Brute force
지원 언어:enko

#Problem

1467B. Hills And Valleys

#Approach

  1. intimidation value를 계산하면서, 언덕과 골짜기에 해당하는 모든 인덱스를 찾습니다.
  2. 인덱스에 속한 모든 인덱스 i에 대해, a∗ia*i를 a∗i−1a*{i-1} 또는 ai+1a_{i+1}로 임시로 변경한 뒤 dif를 계산합니다.
  3. 2단계에서 찾은 최소 dif를 intimidation value에 더합니다.

모든 dif 계산은 인덱스[i−2,i+2][i-2, i+2]만 조회하므로 O(1)O(1)에 이루어집니다.
제약 조건은 1≤n≤3⋅1051 \le n \le 3\cdot10^5입니다.
따라서 여기서는 brute force 접근법을 적용할 수 있습니다.

#Code

/**
 * author: jooncco
 * written: 2021. 1. 17. Sun. 18:43:44 [UTC+9]
 **/

#include <bits/stdc++.h>
using namespace std;
typedef long long     ll;
typedef vector<int>   vi;
typedef deque<int>    di;
typedef pair<int,int> ii;

int t,n,arr[300010];

int howMany(int idx) {
    int cnt= 0;
    for (int i=idx-1; i <= idx+1; ++i) {
        if (i < 1 || i >= n-1) continue;
        if ((arr[i] > arr[i-1] && arr[i] > arr[i+1]) ||
            (arr[i] < arr[i-1] && arr[i] < arr[i+1])) {
            ++cnt;
        }
    }
    return cnt;
}

int main() {

    cin >> t;
    while (t--) {
        cin >> n;
        for (int i=0; i < n; ++i) cin >> arr[i];

        int ans= 0;
        vi indices;
        for (int i=1; i < n-1; ++i) {
            if ((arr[i] > arr[i-1] && arr[i] > arr[i+1]) ||
                (arr[i] < arr[i-1] && arr[i] < arr[i+1])) {
                ++ans;
                indices.push_back(i);
            }
        }

        int dif= 0;
        for (int i=0; i < indices.size(); ++i) {
            int idx= indices[i], orig= arr[idx];
            int before= howMany(idx);

            arr[idx]= max(arr[idx-1],arr[idx+1]);
            dif= min(dif,howMany(idx)-before);

            arr[idx]= min(arr[idx-1],arr[idx+1]);
            dif= min(dif,howMany(idx)-before);

            arr[idx]= orig;
        }
        cout << ans+dif << "\n";
    }
}

#Complexity

  • Time: O(n)O(n)
  • Space: O(n)O(n)