1898 이전 수열은 어떤 수열일까

하나씩 하나씩 백트래킹하면 시간초과가 난다.

단적이지만 예제를 보면 간단한 법칙이 보인다. (8,7)의 자리가 바뀌고, (5,4), (2,3)의 자리가 바뀐다.

앞부터 차례대로 -1,0,+1의 숫자가 사용되었는지 확인 후 swap하는 방식으로 하면 풀린다.

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, t, a[50001];
bool c[50001], d[50001];
 
bool solve(int x) {
    if (x == n) return true;
    if (d[x]) return solve(x + 1);
    for (int i = -1; i < 2; i++) {
        if (!c[a[x] + i] && a[x] + i > 0) {
            int target = x;
            for (int j = x + 1; j < n; j++) if (a[j] == a[x] + i) {
                target = j;
                break;
            }
            c[a[x]] = c[a[target]] = 1;
            d[target] = 1;
            swap(a[x], a[target]);
            if (solve(x + 1)) return true;
            c[a[x]] = c[a[target]] = 0;
            swap(a[x], a[target]);
            d[target] = 0;
        }
    }
    return false;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) 
        scanf("%d", &a[i]);
    solve(0);
    for (int i = 0; i < n; i++) printf("%d\n", a[i]);
    return 0;
}