백준 1722 - 순열의 순서

문제 설명

1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.

임의의 순열은 정렬을 할 수 있다. 예를 들어  N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….

N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/1722

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 순열의 순서는 정해져 있고 두 가지 쿼리를 처리하면 된다.

• K가 주어지면 K번째 순열을 출력
• 순열이 주어지면 몇 번째인지 출력

 

우선, 가장 간단한 방법으로는 모든 순열을 만들고 쿼리를 처리하는 것이다.

하지만, 이 경우에는 시간 초과가 발생한다.

 

해결 방법은 규칙을 찾는 것이다.

순열의 순서를 신경쓰지 않고 일단 경우의 수부터 확인해 보자.

{1, 2, 3, 4}로 만들 수 있는 순열은 총 24가지이다.

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 하나당 6가지의 경우의 수가 존재한다.

이는 팩토리얼과 관련이 있다.

4자리 순열은 총 24가지로 4! 과 일치한다.

또한, 가장 앞자리로 그룹지어진 수열은 총 3자리의 순열을 만드는 것이며 이는 각 그룹당 6개로 3! 과 일치한다.

즉, 자리수로 놓고 본다면 4!, 3!, 2!, 1!으로 생각할 수 있다는 것이다.

이러한 논리를 적용하면 K번째 순열과 순열이 몇 번째인지 구하는 것이 가능하다.

 

우선, 팩토리얼을 모두 구해준다.(N <= 20)

cin >> N;

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

 

K가 주어지면 순열을 구하는 것부터 처리해 보자.

가장 앞자리를 구하는 것을 해보면 뒤에는 동일하게 처리할 수 있다.

앞의 예시를 그대로 적용해보면 가장 앞자리는 K가 주어졌을 때 6으로 나눠보면 몫+1이 가장 앞자리가 된다.

예를 들어, K = 3이라고 하면 앞자리는 1이 분명하다.

K = 7이라면 앞자리는 2일 것이다.

즉, (N-1)! 만큼 계속 빼다 보면 K보다 (N-1)! 이 커질 때 해당 자리의 숫자가 결정된다.

cin >> K;

for (int i = N - 1; i >= 0; i--)
{
    for (int j = 1; j <= N; j++)
    {
        if (v[j]) continue;

        if (fact[i] < K)
        {
            K -= fact[i];
        }
        else
        {
            cout << j << " ";
            v[j] = true;
            break;
        }
    }
}

 

이제, 수열이 주어졌을 때 몇 번째인지 구해보자.

이는  위의 작업을 반대로 적용하면 된다.

이미 수열에 포함된 숫자가 아니라면 (N-1)!씩 더해나가면 된다.

int t;
K = 0;

for (int i = N - 1; i >= 0; i--)
{
    cin >> t;

    for (int j = 1; j < t; j++)
    {
        if (!v[j]) K += fact[i];
    }

    v[t] = true;
}

cout << K + 1;

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
long long N, K, CMD;
vector<long long> fact(20);
vector<bool> v(21, false);

int main() 
{
    INPUT_OPTIMIZE;

    cin >> N;

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

    cin >> CMD;
    if (CMD == 1)
    {
        cin >> K;

        for (int i = N - 1; i >= 0; i--)
        {
            for (int j = 1; j <= N; j++)
            {
                if (v[j]) continue;

                if (fact[i] < K)
                {
                    K -= fact[i];
                }
                else
                {
                    cout << j << " ";
                    v[j] = true;
                    break;
                }
            }
        }
    }
    else
    {
        //K출력
        int t;
        K = 0;

        for (int i = N - 1; i >= 0; i--)
        {
            cin >> t;

            for (int j = 1; j < t; j++)
            {
                if (!v[j]) K += fact[i];
            }

            v[t] = true;
        }

        cout << K + 1;
    }

    return 0;
}

---