[BOJ/C++] 1722 순열의 순서

조합론을 이용한 문제로 N이 최대 20! 이므로 long long을
사용해야 합니다.

순열이 사전 순으로 되어있기 때문에 몇 번째에 어떤 순열이 있는지 유추해볼 수 있습니다.

N이 4인 경우로 예시를 들어보겠습니다.

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2

2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1

3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1

4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

• 순열의 첫 번째 자리엔 {1, 2, 3, 4} 4가지가 올 수 있고 각각 6개의 경우의 수가 있습니다.
• 각각 1~6 번째, 7~12번째, 13~18 번째, 17~24번째 사이에 존재한다는 것을 알 수 있습니다.
• 6으로 나눈 몫이 각각 1, 2, 3, 4보다 작거나 같을 때 해당 범위에 순열이 존재함을 유추해볼 수 있습니다.

3번째 순열 {1 3 2 4}로 예를 들어보겠습니다.

• 순열의 첫 번째가 정해진 경우 {1, , , ,} 나머지 3자리에 올 수 있는 경우의 수는 3! = 6개 입니다.

• N개의 순열이라고 할 때 (N-1)!로 나눈 몫으로 순열의 첫 번째 자리를 알 수 있습니다.

• 즉 (N-1)! >= K 를 만족하는 구간에 존재합니다.

  • 1*(N-1)! >= K를 만족하는 첫 번째 순열은 1
  • 2*(N-1)! >= K를 만족하는 첫 번째 순열은 2입니다.

• 즉 cnt*(N-1)!의 배수와 K를 비교하면 됩니다

• 이후 cnt*(N-1)!의 경우의 수 만큼 K에서 빼줍니다.

• 예를 들어, 10번째 라면 수열의 첫 번째 수는 2일 것이고 1인 6개 경우의 수를 빼준 것입니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

static bool visited[21]={false};
static int64 factorial[21];
static int result[21];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    factorial[0] = 1;

    for(int i=1; i<N; i++)
    {
        factorial[i] = factorial[i - 1] * i;
    }

    if(Q == 1)
    {
        int64 K;
        cin >> K;

        for(int i=1; i<=N; i++)
        {
            int cnt = 1;

            while(cnt * factorial[N - i] < K)
                cnt++;

            K -= (cnt - 1) * factorial[N - i];
            for(int j=1; j<=N; j++)
            {
                if (visited[j])
                    continue;

                cnt--;

                if (cnt == 0)
                {
                    result[i] = j;
                    visited[j] = true;
                    break;
                }
            }
        }
        for (int i = 1; i <= N; i++)
        {
            cout << result[i] << ' ';
        }
    }
    else
    {
        int64 K = 1;
		for(int i=1; i<=N; i++)
		{
            int cnt = 0;
            int64 temp;
            cin >> temp;

            for(int j=1; j<temp; j++)
            {
                if (!visited[j])
                    cnt++;
            }

            K += cnt * factorial[N - i];
            visited[temp] = true;
		}

        cout << K;
    }


    return 0;
}