Baekjoon 1722 순열의 순서

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

소스결과 1988 KB / 0 ms

출처 Baekjoon

언어 C++ 17

분류 수학, 순열

 

설명

1 ~ N의 수열에 대해서 K번째 순열 또는 순열이 주어질 때 해당 값이 몇번째 순열인지 출력해라.

 

정말 이해하는데 오래 걸린 문제다.

https://wjdgus2951.tistory.com/66 해당 블로그를 참고했다. 

[Baekjoon] 1722번 순열의 순서

 

분할 정복이 기본 원칙인 문제인거 같다.

첫번째 자리는 N개가 올 수 있고, 그 이후 자리는 N - i 개의 문자가 올 수 있다.

따라서 각 자리에서 생성 할 수 있는 순열의 개수는 N!개가 된다.

이 내용을 이해는 했지만 구현에 실패해 다른 블로그를 참고하고 한수 배웠다.

 

알고리즘

자세한 내용은 블로그의 링크를 참고하시기 바랍니다.

1. 최대 20이므로 20factorial까지의 값을 DP를 통하여 초기화를 한다.

2. 순열이 주어지는 경우

 - 각 자리마다 factorial값과 비교하여 각 자리를 채워나간다.

3. 번호가 주어지는 경우

 - 2번의 반대에 해당한다 N - i 번째의 위치의 factorial 값을 계속 빼나가면서 몇번째 번호인지 확인한다.

 - 번호가 발견되면 해당 번호를 방문처리하고 다음 위치로 이동한다.

 

소스코드

 

#include <iostream>
#include <vector>

using namespace std;

const short MAX = 20;

typedef long long ll;

ll facto[MAX + 1] = { 1 };

void init() {

	for (int i = 1; i < MAX + 1; i++)
		facto[i] = facto[i - 1] * i;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n; cin >> n;

	int order; cin >> order;
	init();

	vector<bool> checker(n + 1, false);

	if (order == 1) {
		ll k; cin >> k;

		vector<int> res(n);


		for (int i = 0; i < n; i++) {

			for (int j = 1; j < n + 1; j++)
			{
				if (checker[j])
					continue;

				if (facto[n - i - 1] < k) k -= facto[n - i - 1];
				else {
					res[i] = j;
					checker[j] = true;
					break;
				}
			}
		}

		for (int i = 0; i < n; i++)
			cout << res[i] << ' ';

	}
	else {
		ll ans = 0;

		vector<int> permu(n);

		for (int i = 0; i < n; i++)
			cin >> permu[i];

		for (int i = 0; i < n; i++) {

			for (int j = 1; j < permu[i]; j++) {
				if (!checker[j])
					ans += facto[n - i - 1];
			}

			checker[permu[i]] = true;
		}

		cout << ans + 1;
	}

	return 0;
}