[백준] 순열의 순서 c++

순열의 순서

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

16236

4892

3784

34.155%

문제

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개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.

---

#include<iostream>

using namespace std;

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

int main()
{
	cin >> N >> Q;
	F[0] = 1;

	// 각 자리에서 만들 수 있는 경우의 수 계산 (팩토리얼 계산)
	for (int i = 1; i <= N; i++)
	{
		F[i] = F[i - 1] * i;
	}

	if (Q == 1) // Q가 1이면 K번째 순열을 찾아 출력
	{
		long K;
		cin >> K;

		// 순열을 차례대로 계산ㄴ
		for (int i = 1; i <= N; i++)
		{
			int cnt = 1; // cnt: 현재 자리에서 선택할 수 있는 숫자의 순서

			for (int j = 1; j <= N; j++)
			{
				if (Visited[j])
				{
					continue;
				}

				// K가 현재 선택 가능한 범위 내에 있으면 해당 숫자를 선택
				if (K <= cnt * F[N - i])
				{
					K -= ((cnt - 1) * F[N - i]); // K번째 순열 번호에서 이전 범위 차감
					S[i] = j;
					Visited[j] = true;
					break;
				}

				cnt++; // cnt를 증가시켜 선택할 수 있는 숫자 순서대로 검사
			}
		}

		for (int i = 1; i <= N; i++)
		{
			cout << S[i] << " ";
		}
	}
	else // Q가 2이면 주어진 순열에 대한 번호를 계산
	{
		long K = 1;

		for (int i = 1; i <= N; i++)
		{
			cin >> S[i]; // 주어진 순열의 i번째 숫자

			long cnt = 0; // 현재 자리에서 작은 숫자들의 개수를 셈

			for (int j = 1; j < S[i]; j++)
			{
				if (false == Visited[j])
				{
					cnt++; // S[i]보다 작은 숫자 중 아직 선택되지 않은 숫자 개수
				}
			}

			K += cnt * F[N - i]; // 그 숫자들이 차지하는 순열 번호 추가
			Visited[S[i]] = true;
		}

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

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