1722 순열의 순서 (조합론) [Gold V]

1722번: 순열의 순서 (acmicpc.net)

 

3개의 수를 이용해 임의의 순열을 만들고 정렬을 하면

{1, 2, 3}
{1, 3, 2}

{2, 1, 3}
{2, 3, 1}

{3, 1, 2}
{3, 2, 1}

이처럼 정렬을 할  수 있습니다.

이 문제는 2,1,3이 몇번째에 있는지, 5번째에 위치한 순열은 무엇인지 물어보는 문제입니다.

 

경우의 수

1부터 N까지의 수를 임의로 배열한 순열은 N!개가 있습니다.

N * (N - 1) * (N - 2) * .... ... ... * 2 * 1

 

1 ~ 4까지의 수를 임의로 배열한 순열은 1 * 2 * 3 * 4 = 24개

해당 경우의 수를 이용하면 문제를 쉽게 풀 수 있습니다.

 

N = 4, K = 3이라고 할때

3번째에 위치한 순열을 찾는 방법

1이 1번째에 올 경우의 수 = 6 ( 1 ~ 6 )
2가 1번째에 올 경우의 수 = 6 ( 7 ~ 12 )
3이 1번째에 올 경우의 수 = 6 ( 13 ~ 18 )
4가 1번째에 올 경우의 수 = 6 ( 19 ~ 24 )
// 4개 숫자로 만들 수 있는 순열 = 24
// 24 / 4 = 각 숫자당 경우의 수 6

1이 1번째에 올 경우의 수는 6가지가 됩니다.

즉 6번째 순열 까지는 가장 첫번째 숫자가 1입니다. 

K = 3이기 때문에 첫번째 수 = 1

(코드에서는 K와 6과 비교해서 작으면 1을 넣음)

 

2가 2번째에 올 경우의 수 = 2 ( 1 ~ 2 )
3이 2번째에 올 경우의 수 = 2 ( 3 ~ 4 )
4가 2번째에 올 경우의 수 = 2 ( 5 ~ 6 )
// 3개 숫자로 만들 수 있는 순열 = 6
// 6 / 3 = 각 숫자당 경우의 수 2

K = 3이기 때문에 2가 두번 째 숫자에 올 수 없음

즉 두번 째 수 = 3

(코드에서는 K와 경우의 수 2와 비교하고 K가 크면 다음 경우의 수인 4와 비교하여 3을 넣음)

 

2가 3번째에 올 경우의 수 = 2 ( 3 )
4가 3번째에 올 경우의 수 = 2 ( 4 )
// 2개 숫자로 만들 수 있는 순열 = 2
// 2 / 2 = 각 숫자당 경우의 수 1

k = 3이기 때문에 2가 세번째 수

남은 숫자 4가 마지막으로 들어오게 됨(코드에서는)

 

1, 3, 2, 4를 입력받았을때 몇번째인지 체크 하는 방법

1이 1번째에 올 경우의 수 = 6 ( 1 ~ 6 )
2가 1번째에 올 경우의 수 = 6 ( 7 ~ 12 )
3이 1번째에 올 경우의 수 = 6 ( 13 ~ 18 )
4가 1번째에 올 경우의 수 = 6 ( 19 ~ 24 )
// 4개 숫자로 만들 수 있는 순열 = 24
// 24 / 4 = 각 숫자당 경우의 수 6

첫번째 수로 1을 입력 받았으니

1 ~ 6번째 사이의 수라는 것을 알 수 있음

(첫번째 수가 들어왔으니 코드에서는 현재 k = 1로 표시)

2가 2번째에 올 경우의 수 = 2 ( 1 ~ 2 )
3이 2번째에 올 경우의 수 = 2 ( 3 ~ 4 )
4가 2번째에 올 경우의 수 = 2 ( 5 ~ 6 )
// 3개 숫자로 만들 수 있는 순열 = 6
// 6 / 3 = 각 숫자당 경우의 수 2

2번째 수로 3을 입력 받았으니 

3 ~ 4의 숫자라는 것을 알 수 있음

(코드에서는 1 ~ 2를 건너 뛰었으니 k = 3으로 표시)

2가 3번째에 올 경우의 수 = 2 ( 3 )
4가 3번째에 올 경우의 수 = 2 ( 4 )
// 2개 숫자로 만들 수 있는 순열 = 2
// 2 / 2 = 각 숫자당 경우의 수 1

3번째 수로 2를 입력받았으니

3번째 숫자라는 것을 알게됨

(첫번째 수가 들어왔으니 코드에서는 k 변화 없이 k = 3)

정답 코드 

#include <iostream>
#include <vector>

using namespace std;

static int N, Q;
static long F[21], S[21];
static bool visited[21] = { false };

void answer1();
void answer2();

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> Q;

	F[0] = 1;
	for (int i = 1; i < N; i++) {
		F[i] = F[i - 1] * i;
	}

	if (Q == 1) {
		answer1();
	}
	else if (Q == 2) {
		answer2();
	}
}

 

 

void answer1() 
{
	long K;
	cin >> K; 

	for (int i = 1; i <= N; i++) 
	{
		for (int j = 1, cnt = 1; i <= N; j++)
		{
			if (visited[j])
				continue;

			if (K <= F[N - i] * cnt) {
				K -= F[N - i] * (cnt - 1);
				S[i] = j;
				visited[j] = true;
				break;
			}
			cnt++;
		}
	}

	for (int i = 1; i <= N; i++)
		cout << S[i] << " ";
}

void answer2()
{
	long K = 1;
	for (int i = 1; i <= N; i++)
	{
		cin >> S[i];
		int cnt = 0;
		for (int j = 1; j < S[i]; j++)
		{
			if (visited[j] == false)
				cnt++;
		}
		K += F[N - i] * cnt; 
		visited[S[i]] = true;
	}

	cout << K << "\n";
}