백준 문제 1722번 순열의 순서 문제풀이 c++

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

1722번: 순열의 순서

문제해석

 

이런 문제는 예시하나 들어서 규칙찾아내서 작성하는게 편한거같다.

케이스 2번부터보자.

4 2

3 2 1 4 가 입력이 주어졌을 경우를 예를들어보자.

 

처음에 작은 순서대로 1 2 3 4 가있고 3이 처음 수란것은 3!만큼 두번 움직였기때문에 3이나온것이다.

그래서 여기서 2*3!=12

 

3을 사용하였으니 그 다음 작은 순서대로 1 2 4 가있다.

2번째 수로 2란것은 2!만큼 한번 움직인 것이기 때문에 여기서 1*2!=2

 

이제 작은 순서대로 1 4가 있다.

3번째 수로 1이므로 1!만큼 0번 움직인 것이기 때문에 여기서 0*1!=0

 

마지막은 자동으로 넣으므로 계산하지않는다

12+2+0=14이고 14번째 순열 바로 다음 순열이 3 2 1 4인것이다.

따라서 3 2 1 4는 14+1=15번째 순열이 된다.

 

이제 이 방법을 역으로 생각해서 케이스 1번을 보자

4 1

15 가 입력으로 주어졌을 경우 예를 들어보자. 바로 위의 역이다.

먼저 15에서 1을 빼준다. 14가됨

 

14를 팩토리얼의 배수의 로 덧셈꼴 로 나타내면 끝난다.

팩토리얼의 배수란 x*y! (0<=x<=y) 이런형태이다. 

14를 이 형태로 나타내면 14=2*3!+1*2!+0*1! 이 되고 

3!에 곱해진수가 2란뜻은 1 2 3 4 중에서 (2+1)번째로 작은 수를 출력하란 뜻이 된다.

1 2 3 4중 3번째로 작은수는 3 남은수는 1 2 4

이 같은 방식으로 1 2 4중 (1+1)번째로 작은 수는 2 남은수는 1 4

1 4중 (0+1)번째로 작은수는 1 

마지막은 자동으로 4 

따라서 3 2 1 4가 답이된다.

 

이 과정을 바탕으로 코드를 작성하였는데 좀 복잡하게 짠듯한 느낌이든다.

작은 순서대로 계속 정렬하는것이 귀찮기 때문에 set내에서 자동정렬해주기때문에 set자료 구조를 사용하였다.

 

코드

 

#include <iostream>
#include <vector>
#include <set>
#include <string>
typedef long long int ll;
using namespace std;
void case1(ll n);
void case2(ll n);
ll check(ll n);
set <ll> s;
vector <ll> v;
ll ftr[21];
ll a[21];
int main(){
	cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ftr[0]=1;
    for(ll i=1; i<21; i++)
    {
        ftr[i]=i*ftr[i-1];
    }
    ll n,input;
    cin>>n>>input;
    for(ll i=1; i<=n; i++)
    {
        s.insert(i);
    }
    if(input==1)
    {
        case1(n);
    }
    else if(input==2)
    {
        case2(n);
    }
}
void case1(ll n){
    ll k;
    cin>>k;
    k--;
    ll index=check(k);
    for(ll i=0; i<n-1-index; i++)
    {
        v.push_back(*s.begin());
        s.erase(s.begin());
    }
    while(k>0)
    {
        index=check(k);

        n=n-index;
        auto iter=s.begin();
        for(ll i=0; i<k/ftr[index]; i++)
        {
            iter++;
        }
        v.push_back(*iter);
        s.erase(iter);
        k=k-ftr[index]*(k/ftr[index]);
        ll after=check(k);
        for(ll i=index; i>1+after; i--)
        {
            v.push_back(*s.begin());
            s.erase(s.begin());
        }
    }
    for(auto iter=s.begin(); iter!=s.end(); iter++)
    {
        v.push_back(*iter);
    }
    for(ll i=0; i<v.size(); i++)
    {
        cout<<v[i]<<" ";
    }
}
void case2(ll n){
    for(ll i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    ll ans=0;
    for(ll i=1; i<=n; i++)
    {
        auto iter2=s.find(a[i]);
        ll cnt=0;
        for(auto iter=s.begin(); iter!=s.end(); iter++)
        {
            if(*iter==*iter2)
            {
                s.erase(iter);
                break;
            }
            else
            {
                cnt++;
            }
        }
        ans=ans+cnt*ftr[s.size()];
    }
    ans++;
    cout<<ans;
}
ll check(ll n){
    for(ll i=1; i<21; i++)
    {
        if(ftr[i]<=n&&n<ftr[i+1])
        {
            return i;
        }
    }
}