백준 25287번 순열 정렬 - C++ 풀이

---

 

1. 앞에서부터 시작하여 이전 수보다 크거나 같으면서 최대한 작은 수로 채워나간다.

 

1. 앞에서부터 시작하여 이전 수보다 크거나 같으면서 최대한 작은 수로 채워나간다.

 감소하지 않으려면 앞에 있는 수를 최대한 작게 만드는 것이 최적이다. 앞(왼쪽)부터 차례로 i와 N-i+1 중에서 더 작은 수로 채워나가면 된다. 단, 감소하지 않아야 하므로 이전 수보다는 크거나 같아야 한다. 만약 i와 N-i+1 모두 이전 수보다 작다면 감소하지 않도록 만드는 것이 불가능한 경우이다.

 

반응형

---

#include <iostream>
#include <vector>

using namespace std;

bool check(vector<int>& A) {
    int N = A.size();
    
    for (int i=0; i<N; i++) {
        int minCand = min(A[i], N-A[i]+1);
        int maxCand = max(A[i], N-A[i]+1);
        
        if (i == 0) A[i] = minCand;
        else {
            if (minCand < A[i-1]) {
                if (maxCand < A[i-1]) return false;
                else A[i] = maxCand;
            }
            else A[i] = minCand;
        }
    }
    
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        
        vector<int> A(N, 0);
        for (int i=0; i<N; i++) cin >> A[i];
        
        if (check(A)) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}