백준 22887, Reversort Engineering

개요

문제 링크
골드 5, 정렬, 구성적
i의 위치를 찾아 뒤집으며 정렬할 때 뒤집는 부분수열의 길이의 합이 C가 되는 수열 구하기

---

접근

1. 재밌는 구성적 문제, 코포의 단골문제이다. 핵심은 만약 i를 찾아 뒤집었다면, a[i]=i를 항상 만족하고, j<i인 j에 대해서도 a[j]=j를 항상 만족한다는 것이다.

2. 그럼 배열된 수열을 가지고 역으로 뒤집어서 처음 상태를 유추해보자. 먼저 뒤집을 배열들의 길이를 생각해야 하는데, 최소는 모두 1인 경우로 n-1이 된다. 최대는? n=7인 경우를 생각해보면 1일때 7, 2일때 6... 해서 6일때 2까지 가 된다. 더 자세히 나타내면

    2 4 6 7 5 3 1
    1 3 5 7 6 4 2 (7, 전체 7)
    1 2 4 6 7 5 3 (6, 전체 13)
    1 2 3 5 7 6 4 (5, 전체 18)
    1 2 3 4 6 7 5 (4, 전체 22)
    1 2 3 4 5 7 6 (3, 전체 25)
    1 2 3 4 5 6 7 (2, 전체 27)

   이렇게 되는데, 매번 정렬되어야 할 원소를 맨 뒤에 두는 방식이라 생각하면 된다. 마지막 6을 정렬하면서 7은 자동으로 정렬되므로 최댓값은 n*(n+1)/2-1이 된다.

3. 그럼 최대 최소를 벗어나면 IMPOSSIBLE을 출력하면 되고, 그 내부에서는 사실 어떻게 정렬하든 상관이 없는데, 작은 원소를 가장 길게 뒤집는 방식을 사용해보자.

   1. 이렇게 하는 이유는, 만약 어떤 i에 대해 i의 인덱스가 j라면 (i,j)까지를 뒤집을 것이다. 그럼 i를 포함해 뒤집는 배열의 길이를 len[i] (=j-i+1)라고 하면 정렬된 배열에서 원 배열을 복원할 때 (i,i+len[i]-1)을 뒤집는 것으로 바꿔서 생각할 수 있다.

   2. 그런데 원 배열을 복원할 때 길이가 단조감소 형태라면 복원된 배열에서 Reversort를 진행할 때 i+len[i]-1 이후의 배열은 이미 정렬된 상태가 된다. 이게 참 어려운데 예시를 보자.

        7, 18
        // 할당 : 7,6,2,1,1,1
        // 복원
        1 2 3 4 5 6 7
        // n=6) (6, 6+len[6]-1) = (6,6)
        // n=5,4도 동일, 4까지 배열은 그대로
        1 2 3 4 5 6 7
        // n=3) (3, 3+len[3]-1) = (3,4) 뒤집음
        1 2 4 3 5 6 7
        // n=2) (2, 2+len[2]-1) = (2,7) 뒤집음
        1 7 6 5 3 4 2
        // n=1) (1, 1+len[1]-1) = (1,7) 뒤집음
        2 4 3 5 6 7 1

      만약 이렇게 길이의 할당이 단조감소 형태라면 정렬을 진행할 때 현재 뒤집는 구간 이외 구간이 이미 정렬된 상태를 유지할 수 있게 된다. n=3일 때를 보면 5,6,7이 정렬되어 있는 것이다.

      3. 이렇게 되면 원배열을 복원할 때 계속 (i, i+len[i]-1)을 해주기만 해도 된다. 왜냐? 뒤에 배열은 이미 정렬되어 있기 때문이다. 그리고 len[i]의 할당은 i가 가질 수 있는 최대 길이를 할당하면 된다. 최대길이는? 나머지를 1로 두었을 때 길이와 남은 배열의 길이의 최솟값이 되겠다.

추가로 c++의 소소한 팁인데 operator를 통해 vector의 cout을 정의할 수 있다. 빠른 코딩에 유리하니 잘 사용해보자.

---

Pseudo code

if (c<n-1) return false;
if (c>n*(n+1)/2-1) return false;
for (i=1~n)
    leftMax = c-(n-1-i) // 나머지를 1로 두었을 때
    leftLength = (n-i+1) // 오른쪽에 남아있는 길이
    len[i] = min(leftMax, leftLength)
    c -= len[i]
for (i=n-1~1) // 역순으로 복원
    reverse(ans+i-1, ans+i-1+len[i]-1)
    // i-1은 i의 인덱스
    // 굳이 포문을 한 번 더 돌면서 i의 위치를 구할 필요가 없다.

---

Source code

#include <bits/stdc++.h>
using namespace std;
using vec = vector<int>;

#define all(a)         a.begin(), a.end()
#define rev(a, i, j) reverse(a.begin() + i, a.begin() + j)
ostream& operator<<(ostream& out, vec& a) {
    for (auto& x : a) out << x << " ";
    return out;
}
bool test() {
    int n, c;
    cin >> n >> c;
    if (c < n - 1 || c > (n * (n + 1)) / 2 - 1)
        return false;
    vec ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = i + 1;
    vec len(n);
    for (int i = 1; i < n; i++) {
        len[i] = c - (n - 1 - i);
        len[i] = min(len[i], n - i + 1);
        c -= len[i];
    }
    for (int i = n - 1; i >= 1; i--) {
        rev(ans, i - 1, i - 1 + len[i]);
    }
    cout << ans << "\n";
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        if (!test()) cout << "IMPOSSIBLE\n";
    }
}