190211 BOJ 1722번 순열의 순서

수학, 구현 문제

며칠을 고민해도 왜 시간 초과가 나는지 몰랐는데

N = 1 인 경우를 체크 안해서 틀린거였다. ㅜㅜ

'엣지 케이스' 체크는 필수라는 것을 다시 한 번 깨달았다.

순열을 직접 나열해보고 구간을 쪼개서 규칙성을 찾으면 되는 문제다.

맨 처음에 오는 숫자가 뭐 일 때 몇 가지가 있고 그 다음에 올 수 있는 수는 몇 가지......

쪼개 보면 활로가 보인다. 단지 좀 귀찮다.

ex) N = 5 일 때 24번째 순열을 찾아보자.

전체 경우의 수는 5! = 120가지

맨 처음 올 수 있는 숫자들 (편의상 0번째 부터 카운트, 즉 23번째를 찾아야 한다)

1 : (5-1)! = 24가지    0번째 ~ 23번째

2 : (5-1)! = 24가지    24번째 ~ 47번째

3 : (5-1)! = 24가지    48번째 ~ 71번째

4 : (5-1)! = 24가지    72번째 ~ 95번째

5 : (5-1)! = 24가지    96번째 ~ 119번째

여기서 규칙을 찾을 수 있는데 

23을 4! 로 나누면 몫은 0 이다. => 첫번째 구간

25를 4! 로 나누면 몫은 1 이다. => 두번째 구간

49를 4! 로 나누면 몫은 2 이다. => 세번째 구간

73을 4! 로 나누면 몫은 3 이다. => 네번째 구간

97을 4! 로 나누면 몫은 4 이다. => 다섯번째 구간

몫이 0 이므로 첫번째 구간으로 돌입한다.

돌입한 후 모듈러 연산으로 값을 갱신해준다. 

(23 % 24 = 23)

그 다음에 올 수 있는 숫자는 4가지

1 - 2 : (4-1)! = 6가지     1번째 ~ 6번째

1 - 3 : (4-1)! = 6가지     7번째 ~ 12번째

1 - 4 : (4-1)! = 6가지    13번째 ~ 18번째

1 - 5 : (4-1)! = 6가지    19번째 ~ 24번째

현재 값 : 23

23을 3! 로 나누면 몫은 3 이다. => 네번째 구간 돌입

값 갱신

(23 % 6 = 5)

그 다음에 올 수 있는 숫자는 3가지

1 - 5 - 2 : (3-1)! = 2가지 0번째 ~ 1번째

1 - 5 - 3 : (3-1)! = 2가지 2번째 ~ 3번째

1 - 5 - 4 : (3-1)! = 2가지 4번째 ~ 5번째

5를 2! 로 나누면 몫은 2 이다. => 세번째 구간 돌입

값 갱신 

(5 % 2 = 1)

그 다음에 올 수 있는 숫자는 2가지

1 - 5 - 4 - 2 : (2-1)! = 1가지 0번째 ~ 1번째

1 - 5 - 4 - 3 : (2-1)! = 1가지 2번째 ~ 3번째

1을 1로 나누면 몫은 1 이다. => 두번째 구간 돌입 => 종료. (마지막 자리는 자동적으로 결정되므로)

N = 5 일 때 24번째 순열

1 - 5 - 4 - 3 - 2

주어진 순열이 몇번째 인지 구하는 방법도 위와 비슷하다... 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define endl '\n'
#define ll long long
#define un unsigned
#define mp(a,b) make_pair(a,b)
#define sws ios::sync_with_stdio(false)
#define MAX 200000000
using namespace std;
int N, k;
un ll x;
int used[21];
int ans[21];
un ll fact[21];
int main() {
    cin >> N;
    cin >> k;
    fact[0] = 1;
    fact[1] = 1;
    FOR(i, 2, 20) fact[i] = fact[i - 1] * i;
    if (k == 1) {
        cin >> x; 
        x--; 
        un ll rng = x / fact[N - 1];
        int idx = 0;
        ans[idx++] = rng + 1;
        used[rng + 1] = 1;
        rng = x % fact[N - 1];
        int M = N - 1; 
        un ll nrng;
        while (M > 1) {
            vector<int> v;
            FOR(i, 1, N + 1) if (!used[i]) v.push_back(i);
            nrng = rng / fact[M - 1];
            ans[idx++] = v[nrng];
            used[v[nrng]] = 1;
            rng %= fact[M - 1];
            M--;
        }
        FOR(i, 1, N + 1) if (!used[i]) {
            ans[idx++] = i;
            break;
        }
        FOR(i, 0, idx) cout << ans[i] << ' ';
    }
 
 
    else {
        FOR(i, 0, N) cin >> ans[i];
        int M = N - 1;
        un ll cnt = fact[N-1] * (ans[0] - 1);
        un ll rng;
        used[ans[0]] = 1;
        FOR(k,1,N) {
            vector<int> v;
            FOR(i, 1, N + 1) if (!used[i]) v.push_back(i);
            int x = find(v.begin(), v.end(), ans[k]) - v.begin();
            used[v[x]] = 1;
            cnt += fact[M - 1] * x;
            M--;
        }
        cout << cnt + 1;
    }
}