BOJ 17432 : 정렬

• 문제 링크 : boj.kr/17432
• 난이도 : G3
• 태그 : 해 구성하기

17432번: 정렬

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while(T--) {
        int n, m;
        cin >> n >> m;
        vector<int> arr(n+1, 0);
        for(int i = n; i > 0; i--) {
            if(m >= i-1) {
                m -= i-1;
                arr[n-i+1] = 1;
            }
        }
        for(int i = 1; i <= n; i++) {
            if(!arr[i]) cout << i << " ";
        }
        for(int i = n; i > 0; i--) {
            if(arr[i]) cout << i << " ";
        }
        cout << "\n";
    }

    return 0;
}

---

풀이

결론부터 말하자면 문제의 핵심은 정렬된 상태에서 어떤 정수를 얼만큼 뒤로 보낼지 정하는 것이다.

 

우선 cnt가 어떤 값을 나타내는지를 알아야 한다.

우선 의사코드는 삽입 정렬의 과정을 나타낸다. 이때 cnt는 삽입 정렬을 위해 원소를 이동한 횟수를 의미한다.

이는 $i < j$일때, $a[i] > a[j]$인 i,j의 순서쌍의 수와 같다.

 

이제 원소를 이동해보며 cnt값의 변화를 살펴보자.

1, 2, 3, 4, 5로 정렬된 순열이 존재한다고 하자.

앞의 순열에서 4를 맨 뒤로 보내면 순열은 1, 2, 3, 5, 4가 되고 cnt 값이 1이 된다.

앞의 순열에서 1을 맨 뒤로 보내면 순열은 2, 3, 5, 4, 1가 되고 cnt 값이 5가 된다.

이렇게 바뀐 순열을 두 부분으로 나눠서 보면 2, 3, 5 / 4, 1 처럼 나누어 볼 수 있다.

앞부분(2, 3, 5)은 정렬되어 있으므로 cnt 값에 영향을 주지 않는다.

뒷부분(4, 1)은 cnt값에 영향을 주는 부분인데, 각각 자신보다 큰 값이 앞에 얼마나 있는지에 따라 cnt에 값이 더해진다.

 

이제 어떻게 cnt 값이 변화하는지 알았으니 cnt 값을 크게 만드는 원소부터 적절히 뒤로 이동해주면 된다.