[BOJ] 1722. 순열의 순서

문제보고오기

 

 

인풋 분석

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

n과 소문제 번호는 int로 받아도 충분하지만, k의 경우 최대값이 20!이 된다. 10!만 되도 백만이 넘는데. 20팩토리얼이면..?

이렇게 큰 수는  자바면 long을, C/C++이면 long long ( = __int64 <- 언더바가 2개다) 형을 사용하여 입출력을 해야한다.

 

순열

짱구, 철수, 훈이, 맹구가 있을 때, 이 들을 일렬로 세우는 방법을 생각해보자.

(순열을 잘 아는 사람들은 이 부분을 넘어가도 된다.)

짱구 -> 철수 -> 훈이 -> 맹구

짱구 -> 철수 -> 맹구 -> 훈이

짱구 -> 훈이 -> 철수 -> 맹구

짱구 -> 훈이 -> 맹구 -> 철수

짱구 -> 맹구 -> 철수 -> 훈이

짱구 -> 맹구 -> 훈이 -> 철수

철수 -> 짱구 -> 훈이 -> 맹구

…

맹구 -> 훈이 -> 철수 -> 짱구

까지… 일일이 세봤더니 총 24가지가 나왔다.

이렇게 해도 되지만, 순열공식을 사용하면 짱구, 훈이, 철수, 맹구 뿐만 아니라 팡팡 유치원의 모든 아이들까지 모두 포함한 경우의 수를 구할 수도 있다.

나무위키를 통해 순열에 대한 정의를 살펴보았더니 다음과 같았다.

순열의 순서

N = 4 인 경우를 생각해보자.

1이 맨 앞자리에 나왔을 때

나머지 3자리에 3개의 숫자를

집어넣는 경우의 수는 몇 가지가 있을까?

2로 시작한다면?

같은 방법으로 3!만큼 있을 것이다.

1,2,3,4가 첫 번째 순열인 것처럼 숫자가 작을 수록 빠른 순열이다.

따라서 우리가 컴퓨터에게 준 순열이 2, 1, 3, 4 라고 했을 때,

적어도 이 순열은 1 이 맨 앞에 오는 1 [] [] [] 의 경우인 3!만큼보다는 다음의 순열일 것이다.

왜냐하면 그 순열들은 이미 지나쳐간 순열들이기 때문이다.

따라서 몇 번째 순열인지를 알아내기 위해서는 지나친 순열의 개수를 차곡 차곡 쌓아가다 자신이 찾고자 하는 순열을 발견하면 그 개수의 합이 곧 순서가 된다!

따라서 우리는 왼쪽 맨 앞에서부터 숫자를 하나씩 늘려가면서 몇 번째 자리인지 검사해볼 것이다.

 

따라서 개수의 합을 구하기 위해서는 팩토리얼을 미리 계산해둘 필요가 있다.

문제에서는 n의 최대값이 20이기 때문에 19!까지만 계산해두면 된다. 지금 보니 코드는 20!까지 계산해둔 것 같다.

여러분은 19!까지만 계산해두길 바란다!

 

그리고 이미 검사한 숫자는 다음에 검사하지 않기 위해 int visit[21] 이라는 배열에 1부터 20까지의 항이 등록이 되어 있으면 1, 안 되어 있으면 0으로 해둬서 체크할 수 있게 만들어 두자.

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include 
 
int p[21], visit[21] = { 0, };
long long fact[21];
 
int main()
{
	// n 원소의 개수, mode 계산 모드, k는 input 으로 들어오는 순열 순서
	int n, mode = 0;
	long long k = 0;				// n! 이 k로 들어올 수도 있다! 따라서 long long 으로 받아줘야 한다.
	scanf("%d %d", &n, &mode);
 
	fact[0] = 1;					// 0! 은 1이다. 아래의 다음 계산을 위해서 0으로 넣는 오류를 범하지 말아야한다.
	for (int i = 1; i <= n-1; i++) {
		fact[i] = i * fact[i - 1];
	}
 
	if (mode == 1)
	{
		scanf("%lld", &k);
 
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (visit[j]) continue;			// 이미 p[i]에 등록한 숫자는 넘어간다.
				if (fact[n - i] >= k)			// 글의 문두에서 보여준 사진을 코드로 바꾼 것이다.
				{	
					p[i] = j;					// 현재 자신이 검사하고 있는 숫자보다 크거나 같으면 
					visit[j] = 1;				// k는 그 범위 안에 있는 숫자이므로 이 숫자를 p[i]에 넣어야한다.	
					printf("%d ", p[i]);		// 그리고 다음에도 검사하지 않기 위해 방문 표시를 해주자.
					break;						// p[i]번째가 등록되었으므로 다음 자릿수로 넘어가서 검사를 해보자.
				}
				else k -= fact[n - i];			// 만약 k가 i번째 자리에 j를 넣었을 때 만들 수 있는 경우의 수보다 더 크다면
			}									// 우리는 그 숫자를 지나쳐 가야한다. 이는 k에서 n-i ! 만큼을 뺀 것과 같다!
		}
	}
 
	else
	{
		for (int i = 1; i <= n; i++)
			scanf("%d", &p[i]);
 
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (visit[j]) continue;
				if (p[i] <= j)
				{
					visit[j] = 1;
					break;
				}
				else k += fact[n - i];			// 주어진 순열에서 검사중인 자릿수의 값이 j보다 크다면 j보다 작거나 같은 경우의 수 만큼을 k에 더해서 이미 지나친
			}									// 수들을 쌓아나가야만 순서를 알아낼 수 있을 것이다.
		}
		printf("%lld\n", k + 1);				// 이렇게 계산하다 보면 1, 3, 2, 4 를 예로 들었을 때, 1, [], [], [] 에서 k는 아무런 변화가 없고
	}											// 1, 2, [], [] 에서 2는 3보다 작기 때문에 k에 2!만큼이 누적된다.
												// 1, 3, [], [] 이 되면 안쪽 for문을 탈출하고 1, 3, 2, [] 를 거쳐, 1,3,2,4 까지 거쳐 for문을 탈출하게 되는데
	return 0;									// 이 과정에서 1 3 2 4 자신을 더하지 않기 때문에 자기 자신을 더해주도록 하자.
}