[Gold / 1722] 순열의 순서

문제 링크

---

🔷 분류

수학, 구현, 조합론

✒️ 문제 설명

1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.

임의의 순열은 정렬을 할 수 있다. 예를 들어 N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….

N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오.

⬅️ 입력

첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다.

➡️ 출력

k번째 수열을 나타내는 N개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.

💻 코드 (C++)

#include <iostream>
using namespace std;

long A[21];
int ans[21];
bool vis[21];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	A[0] = 1;
	for(int i = 1; i <= n; i++) { // 팩토리얼 초기화
		A[i] = A[i-1] * i;
	}
	
	int q; // 소문제 번호
	cin >> q;
	
	if(q == 1) { // k 번째 순열 찾기
		long k;
		cin >> k;
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1, cnt = 1; j <= n; j++) {
				if(vis[j]) continue; // 이미 사용한 숫자면 다음 loop
				
				// 주어진 K에 따라 각 자리에 들어갈 수 있는 수 찾기
				if(k <= cnt * A[n - i]) {
					k -= ((cnt - 1) * A[n - i]);
					ans[i] = j;
					vis[j] = true;
					break;
				}
				cnt++;
			}
		}
		
		for(int i = 1; i <= n; i++) { // 정답 출력
			cout << ans[i] << " ";
		}
	}
	
	else { // 주어진 순열이 몇 번째 순열인지 구하기
		long k = 1;
		
		for(int i = 1; i <= n; i++) {
			cin >> ans[i];
			long cnt = 0;
			
			for(int j = 1; j < ans[i]; j++) {
				if(vis[j] == false) {
					cnt++; // 미사용 숫자 개수만큼 카운트
				}
			}
			
			k += cnt * A[n - i]; // 자릿수 개수에 따라 순서 더하기
			vis[ans[i]] = true;
		}
		cout << k;
	}				
	return 0;
}