[C/C++] 백준 #1722 순열의 순서(수학)

이번 문제는 순열의 순서를 아는 것입니다.

순열 경우의 수는 N이 주어지면, \(N!\)로 아주 큰 수가 됩니다.  순열의 경우의 수가 팩토리얼이라는 것은 아주 중요합니다.

 

우리가 10진수를 생각한다면, N자리의 숫자는 \(10^N\)개의 경우의 수를 가집니다.  이를 이용하면, 우리가 주어진 수가 몇번째 10진수인지 아주 쉽게 구할 수 있습니다.  팩토리얼로 이루어진 수도 마찬가지라고 생각하면 됩니다.

 

permutation

N이 4라면 만들 수 있는 순열 수는 24가지가 됩니다.

1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321

이렇게 됩니다.  첫 숫자가 같은 것은 각가 6개씩 4개의 그룹이 되죠.  이를 이용하면, 우리는 몇번째 숫자가 어떤 숫자이고, 어떤 숫자가 주어지면 몇번째인지 알 수 있습니다.  이를 위해서 팩토리얼 값을 미리 계산합니다.  그리고 계산을 편하게 하기 위해서 0부터 시작한다고 생각해야 합니다.

 

예를 들어서 3124는 몇번째 숫자인가를 찾기 위해서는 2013을 생각 하는 것이죠.  다음은 이미 사용한 작은 수는 제거를 해서 숫자를 표기해야 합니다.  그래서 2013은 2000이 됩니다.  첫번째 자리수가 6이므로 12가 되고, 13번째 수가 됩니다.

 

그러면 마찬가지로 17번째 수는 어떻게 될까요?  계산하면 6으로 나누면 몫이 2이므로 첫 숫자는 2가 됩니다.  나머지는 5이므로 두번째 숫자는 2, 세번째 숫자는 0, 마지막 숫자는 0이 되어서 2200이 됩니다.  이번에는 이미 사용된 숫자이면 다음번 숫자를 찾아야 합니다.  그래서 2301이 되고, 최종적으로는 3412이 되죠.

 

이것을 구현한 소스입니다.  소스는 참고용으로 봐주세요.

//-----------------------------------------
//	baekjoon #1722
//		- by Edan
//		- created at 2019-07-03
//-----------------------------------------
#include <stdio.h>

int main()
{
	int cmd, n;
	char v[21] = {0,};
	long long k, f[20];
	scanf("%d", &n);
	f[0] = 1;
	for(int i = 1; i < n; i++) f[i] = i*f[i-1];
	scanf("%d", &cmd);
	if(cmd == 1)
	{
		scanf("%lld", &k);
		k--;
		for(int s = n - 1; s>=0; s--)
		{
			int t = (int)(k / f[s])+1;
			int c = 1;
			while(t) if(v[c]) c++; else c++, t--;
			v[c-1] = 1;
			printf("%d ", c-1);
			k %= f[s];
		}
	}
	else
	{
		int t;
		k = 0;
		for(int s = n - 1; s >= 0; s--)
		{
			scanf("%d", &t);
			int c = 0;
			for(int i = 1; i < t; i++) if(!v[i]) c++;
			v[t] = 1;
			k += c * f[s];
		}
		printf("%lld\n", k+1);
	}
	return 0;
}