Codeforces Round #616 (Div. 2) B. Array Sharpening

입력받는 n개의 수들이 k번째까지 증가하고, k부터 n번째까지 감소하는 수열이라면 해당 배열을 sharpened 라고 한다. 여기서 각수들을 1만큼 무한정 뺄 수 있다.

나는 이 수열을 뺄 수 있을 만큼 다 빼보았을 때 어떤 형태가 되는지 생각해보았다. 간단하게 n이 4와 5일 때를 생각해보았다.

1)n = 4 인경우

0 1 2 0 또는 0 2 1 0 이 된다.

2)n = 5 인경우

0 1 2 1 0 의 경우가 최소가 된다.

위 경우로 미루어보아 홀수의 경우 중앙이 최대값이고, 짝수의 경우는 정확한 중앙이 없으므로 최대값의 위치가 2가지로 나타난다. 이를 정리해 코드로 작성하면 된다.

#include <iostream>
#include <string>

using namespace std;

int main(){
    int t,n;
    cin >> t;
    for (int i = 0; i < t; i ++){
        cin >> n;
        int a[300010];
        for (int j = 0; j < n; j ++){
            cin >> a[j];
        }
        bool isPossible = true;
        
        if(n % 2 == 1){
            for(int j = 0; j <= n/2; j++ ){
                if((a[j] < j ) || (a[n-j-1] < j)){
                    isPossible = false;
                    break;
                }
            }
        } else{
            for(int j = 0; j < n/2; j ++){
                if((a[j] < j) || (a[n-j-1] < j )){
                    isPossible = false;
                    break;
                }
            }
            if((a[n/2-1] < n/2) && (a[n/2] < n/2)){
                isPossible = false;
            }
        }
        cout << (isPossible ? "Yes" : "No") << endl;
    }
    return 0;
}