백준 1722 : 순열의 순서

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

1722번: 순열의 순서

 

n=4일 때의 정렬된 순열을 나열해보겠습니다. (문제와 달리, 각 수와 순열은 0번째부터 시작한다고 가정)

1 2 3 4 - 0번째 순열
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1 - 9번째 순열
2 4 1 3
2 4 3 1

...

 

0번째 수 하나당 6개의 경우의 수가 있습니다.

1번째 수 하나당 2개의 경우의 수가 있습니다.

2번째 수 하나당 ...

 

즉, n에 따라서,

0번째 수 하나당 (n-1)!개의 경우의 수가 있고,

1번째 수 하나당 (n-1-1)!개의 경우의 수가 있고,

2번째 수 하나당 (n-1-1-1)!개의 경우의 수가 있고,

x번째 수 하나당 (n-x-1)!개의 경우의 수가 있습니다.

 

chk[i](숫자 i가 이미 순열에 나타났는지 true or false) 배열을 두고,

9번째 순열을 구해보겠습니다.

 

4개의 숫자에서는, 첫번째 수 하나당 6개의 경우의 수가 있습니다.

9 / 6은 1이므로, 아직 사용되지 않은 숫자 중 1번째 숫자 2를 순열의 첫번째로 구할 수 있습니다.

chk[2] = true로 설정해줍니다.

9 % 6는 3이므로, 순열이 [2 ? ? ?]인 상황에서의 3번째 숫자를 구해주어야 합니다.

 

이제 3개의 숫자가 남습니다.

3개의 숫자에서는, 첫번째 수 하나당 2개의 경우의 수가 있습니다.

3 / 2은 1이므로, 아직 사용되지 않은 숫자 중 1번째 숫자 3을 순열의 두번째로 구할 수 있습니다.

chk[3] = true로 설정해줍니다.

3 % 2는 1이므로, 순열이 [2 3 ? ?]인 상황에서의 1번째 숫자를 구해주어야 합니다.

 

이제 2개의 숫자가 남습니다.

2개의 숫자에서는, 첫번째 수 하나당 1개의 경우의 수가 있습니다.

2 / 1은 2이므로, 아직 사용되지 않은 숫자 중 2번째 숫자 4를 순열의 세번째로 구할 수 있습니다.

chk[4] = true로 설정해줍니다.

2 % 1는 1이므로, 순열이 [2 3 4 ?]인 상황에서의 1번째 숫자를 구해주어야합니다.

 

이제 1개의 숫자가 남습니다.

동일한 방식으로 구해주면, [2 3 4 1]을 얻을 수 있습니다.

 

 

이번에는 역으로, [2 3 4 1]이 몇번째 수열인지 구해보겠습니다.

 

0번째 숫자 2는, 아직 사용되지 않은 숫자 중에서 1번째 숫자입니다.

수 하나당 6개가 있으므로, 이미 앞에는 6 * 1개의 순열이 있습니다.

 

1번째 숫자 3은, 아직 사용되지 않은 숫자 중에서 1번째 숫자입니다.

수 하나당 2개가 있으므로, 이미 앞에는 6 * 1 + 2 * 1개의 순열이 있습니다.

 

2번째 숫자 4는, 아직 사용되지 않은 숫자 중에서 1번째 숫자입니다.

수 하나당 1개가 있으므로, 이미 앞에는 6 * 1 + 2 * 1 + 1 * 1개의 순열이 있습니다.

 

3번째 숫자 1은, 아직 사용되지 않은 숫자 중에서 0번째 숫자 입니다.

수 하나당 1개가 있으므로, 이미 앞에는 6 * 1 + 2 * 1 + 1 * 1 + 1 * 0개의 순열 있습니다.

 

즉, 9번째 순열입니다. 

(문제에서는, 1부터 시작하므로 10번째)

 

위 과정을 코드로 나타내면 다음과 같습니다.

#include <iostream>
using namespace std;

typedef long long ll;

int n, m, a;
bool chk[21];

int findNotUsedNum(int idx) {
	for (int i = 1; i <= 20; i++)
		if (!chk[i] && idx-- == 0) return i;
	return -1;
}

int findNotUsedCnt(int num) {
	int cnt = 0;
	for (int i = 1; i <= 20; i++) {
		if (!chk[i]) {
			if (i == num) return cnt;
			cnt++;
		}
	}
	return cnt;
}

ll factorial(int num) {
	ll res = 1;
	for (int i = 2; i <= num; i++) res *= i;
	return res;
}

int main() {
	cin >> n >> m;
	ll cnt = factorial(n - 1);
	if (m == 1) {
		ll k;
		cin >> k;
		k--;
		while (n--) {
			int num = findNotUsedNum(k / cnt);
			chk[num] = true;
			k = k % cnt;
			cnt = n ? cnt / n : cnt;
			cout << num << " ";
		}
	}
	else {
		ll sum = 1;
		while (n--) {
			cin >> a;
			sum += findNotUsedCnt(a) * cnt;
			cnt = n ? cnt / n : cnt;
			chk[a] = true;
		}
		cout << sum;
	}
}