BOJ 1722 순열의 순서

사용한 알고리즘

수학

알고리즘 설명

위에 조합에서 수식을 만들어 내기 위해서 예시를 들겠다.
ex 1. 1234 -> 2134 와 같이 앞자리 수가 변하기 위해서는 그 사이에 3!(n!)의 경우의 수가 존재한다.
ex 2. 4xxxx 인 경우 3*4! 의 경우의 수가 사이에 존재한다
ex 3. 45xxx 와 같은 경우 3*4!의 경우의 수가 기본적으로 존재하고 5 밑에는 1,2,3인 숫자 3개가 존재하므로 3*3! 가 필요하여 45xxx 에 대해서 3*4! + 3*3! 가 필요하다.
ex 4. 451xx와 같은 경우 숫자 1 이하에 숫자가 존재하지 않으므로 경우의 수 변화가 없다
ex 5. 4513x와 같은 경우 숫자 3 이하에 숫자 2가 존재하므로 1*1! 만큼 더하여 3*4! + 3*3! + 1*1!
ex 6. 45132와 같은 경우 숫자 2 이하에 숫자는 존재하지 않으므로 45132는 (3*4! + 3*3! + 1*1!) + 1번째 숫자이다.
위를 이용하여 역으로 이용하면 K번째 수도 추려낼 수 있다.

풀이

// baekjoon 1722 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

const int MAX_N=21;

int N, cmd;
ll fact[MAX_N], K;
bool visited[MAX_N];

ll factorial(ll x) {
	if (x == 0) return 1;
	if (fact[x]) return fact[x];
	return fact[x] = x*factorial(x-1);
}

int main() {
	scanf("%d", &N);
	scanf("%d", &cmd);

	if (cmd == 1) {
		scanf("%lld", &K);
		K--;
		for (int i=1; i<=N; i++) {
			ll x = K/factorial(N-i);
			for (int j=1; j<=N; j++) {
				if (visited[j]) continue;
				if (!x) {
					visited[j]=true;
					printf("%d ", j);
					break;
				}
				x--;
			}
			K = K%factorial(N-i);
		}
	} else {
		ll ret = 1;
		for (int i=1; i<=N; i++) {
			int x;
			scanf("%d", &x);
			visited[x]=true;
			for (int j=1; j<x; j++)
				if (!visited[j])
					ret += factorial(N-i);
		}
		printf("%lld\n", ret);
	}
	return 0;
}