[Algorithm] Baekjoon 1722번 : 순열의 순서

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

1722번: 순열의 순서

int n, opNum, input;
unsigned long long k;
unsigned long long factorials[20];
int target[21];
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    factorials[0] = 1;
    for (int i = 1; i <= 19; ++i)
    {
        factorials[i] = factorials[i - 1] * i;
    }
 
    cin >> n >> opNum;
    bool visited[21] = { false };
 
    if (opNum == 1)
    {
        cin >> k;
 
        int answer[20] = { 0 };
 
        for (int i = 0; i < n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (visited[j]) continue;
                
                if (factorials[n - i - 1] < k) // 감당했으니 더 큰숫자로 
                {
                    k -= factorials[n - i - 1];
                }
                else
                {
                    answer[i] = j;
                    visited[j] = true;
                    break;
                }
            }
        }
 
        for (int i = 0; i < n; ++i) cout << answer[i] << " ";
    }
    else
    {
        for (int i = 1; i <= n; ++i)
        {
            cin >> target[i];
        }
 
        unsigned long long sum = 1;
        
        for (int i = 1; i <= n; ++i)
        {
            int num = target[i];
            int count = 0;
 
            for (int j = 1; j < num; ++j)
            {
                if (!visited[j]) ++count;
            }
 
            visited[num] = true;
            sum += count * factorials[n - i];
        }
        
        cout << sum;
    }
}

순열의 규칙에 대해서 많이 이해하고 있었다면 쉬웠을거고.. 아니면 골드5보다는 더 어렵다고 체감했을 문제다.

순열의 순서는 무조건 낮은숫자가 맨 먼저라는것을 이용한 문제이다.

 

일단 각 자릿수의 숫자가 '적절한 바로 다음 숫자'로 바뀌려면, 각 자릿수는 10의 n승이니까 n! 의 간격이 있다.

즉 1 2 3 4 에서 2 1 3 4 로 바뀌려면 3!, 즉 6번의 차례가 지나가야 비로소 맨 앞자리가 2가 된다.

 

맨 앞자리만 보면 이렇게 계산하면 될 것 같지만, 이후의 숫자들로 가면 적용되지 않는다.

문제의 순열은 숫자가 한번씩만 쓰이는 순열이기 때문이라는것을 인지해야한다.

그렇기 때문에 해당숫자가 제일 처음숫자(1)과 무작정 몇차이나는지를 계산하고 n!을 곱하는게 아니라, 이미 사용한 숫자가 있을 수 있으니 반복문을 통해 체크해줘야한다.