백준 1722번:순열의 순서

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

1722번: 순열의 순서

 

이 문제를 풀 때 브루트 포스로 next_permutation함수를 쓰면 20!이기 때문에 2초라는 시간을 아득히 넘는다. 즉 이 문제는 브루트포스로 푸는 것이 아니다.

순열의 수는 그 원소 값을 보면 된다.

예시를 들자

3 5 1 4 2 라는 순열이 있다.

그러면 이 순열이 몇 번쨰 인지는 

1 x x x x  4!

2 x x x x  4!

3 1 2 4 5  로 4!*2 가 된다. 이렇게 첫번째 인자를 3으로 했을 때 순열 수다.그 다음도 구하는 방식은 똑같다.

3 1 x x x   3!

3 2 x x x   3!

3 4 x x x   3!

3 5 1 2 4  로 3!*3 이 되고 3 5 1 2 4 라는 순열은 4!*2+3!*3 가 된다 계속 이어서 하자

3 5 1 x x 2!

3 5 1 4 2 로 2!가 된다. 이 때는 왜 원소가 4인데 1  3 을 안하냐면 이미 그 전 배열에서 1 3 을 이미 사용하였기 때문이다.

이렇게 순열의 수를 구하면 된다.

순열의 수를 알고 배열을 구하는 것은 이 방식 반대로 가면 된다.

이제 코드를 보자

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long fac[21];
bool check[21];
long long factorial(int n){             //n의 팩토리얼 저장
    if(n==1){
        fac[1]=1;
        return fac[1];
    }
    fac[n]=n*factorial(n-1);
    return fac[n];
}
int main(){
    int n,num;
    cin >>n>>num;
    factorial(n);
    fac[0]=1;
    vector<int> v(n); 
    if(num==1){                      //1을 누를떄
        long long k;
        cin>>k;
        for(int i=0;i<n;i++){
            for(int j=1;j<=n;j++){  
                if(check[j]==true){                // j 값이 이미 사용되었으면 넘어감
                    continue;
                }
                if(k>fac[n-i-1]){                 //k번이 i번쨰 수열 수 찾을 떄 그 다음 수부터 수열의 수를 빼준다.
                    k-=fac[n-i-1];
                }
                else{
                    v[i]=j;
                    check[j]=true;
                    break;
                }
            }
        }
        for(int i=0;i<n;i++){
            cout << v[i]<< ' ';
        }
    }
    else if(num==2){        //2번 누를때
        long long cnt=1;
        for(int i=0;i<n;i++){
            cin >>v[i];
        }
        for(int i=0;i<n;i++){
            for(int j=1;j<v[i];j++){     //배열값보다 작으면
                if(check[j]==false){     //원소가 사용 안되었으면
                    cnt+=fac[n-i-1];      // 그 다음 배열 원소 순열 수만큼 더함
                }
            }
            check[v[i]]=true;           //그 원소 이미 사용했으니 true저장
        }
        cout << cnt;
    }

}