[백준] 1722 순열의 순서 C++

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

1722번: 순열의 순서

순열 + DP문제입니다.

순열은 nPr이고 n개 중에 r개를 뽑는데 순서를 고려하여 뽑는 경우를 뜻합니다.(사전순 정렬)

문제의 입력 최대값이 20이므로 O(20!)을 가지기에 next_permutation을 사용하면 무조건 시간초과로 틀리기 때문에 시간 복잡도를 줄이기 위해 고민이 필요한 문제인거 같습니다.

 

---

풀이순서

1. 먼저 입력조건에 따라 입력을 받는다.

2. 팩토리얼 값을 담을 fac함수를 초기화를 진행한다.

3. k == 1인 경우 정해지지 않은 앞자리의 값을 찾기 위한 로직을 전개한다.

4. k == 2인 경우 값을 매번 입력받으면서 지금 값이 몇번째 자리인지 구한다.

5. 출력

---

풀이

먼저 k가 1인경우 부터 살펴보도록 하겠습니다.

4

1 7 

위처럼 입력을 받은 경우 7번째오는 순열이 무엇인지 구해야 합니다.

1234 1243 1324 1342 1423 1432 (6개)

2134 2143 2314 2341 2413 2431 (6개)

3124 3142 3214 3241 3412 3421 (6개)

4123 4132 4213 4231 4312 4321 (6개)

이렇게 총 24가지의 경우의 수가 나옵니다.

N이 4인경우 나올 수 있는 총 경우의 수는 4!이며 앞자리가 1이 오는 경우 올 수 있는 경우의 수는 3!입니다.

즉 (N-1)!이고 다른말로 하면 길이가 N인 순열에서 앞자리가 i개 결정되었을 때 (N-i)!개의 경우의 수를 갖습니다.

 

앞자리가 1개 결정되었을 때 (1이라 가정) 1 o o o => o 에 올 수 있는 경우의 수 (4 - 1)! visit배열의 1번 인덱스 방문표시.

앞자리 2개가 결정되었을 때 1 3 o o => o 에 올 수 있는 경우의 수 (4 - 2)! visit배열의 3번 인덱스 방문표시.

...

이런 아이디어로 앞자리 수를 확정하며 풀이가 가능합니다.

 

k가 2인경우에도 k가 1일때의 풀이 방법과 비슷합니다.

for문에서 값을 하나씩 입력받으면서 입력받은 수 만큼 for문을 돌아 cnt값을 늘립니다.

cnt는 앞자리의 값을 확정하기 위한 변수입니다.

가령 가장먼저 3이라는 값을 입력을 받았다고 가정을하면 가장 앞자리가 3이라는 것은 3으로 시작하는 순열의 순서는 최소 3! * 2보다는 크고 18보다는 작거나 같습니다.

여기서 3!에 곲하는 2라는 값을 정해주는 변수가 cnt입니다.

이 cnt값을 fac[n - 1]과 곱하여 p의 값을 업데이트 해주고 visit[ret[i]]는 방문처리를 해줍니다.

---

코드

#include <vector>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <queue>
#include <limits.h>
#include <memory.h>
#include <sstream>
using namespace std;

#define endl "\n"
#define ll long long
#define INF 987654321

typedef pair<int, int> Pair;
typedef tuple<int, int, int> Tuple;

int n, k;
ll fac[21]; ll ret[21];
bool visit[21];

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

	cin >> n >> k;

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

	if (k == 1)
	{
		ll p; cin >> p;
		for (int i = 1; i <= n; ++i)
		{
			int cnt = 1;

			for (int j = 1; j <= n; ++j)
			{
				if (visit[j]) continue;
				if (p <= cnt * fac[n - i])
				{
					p -= ((cnt - 1) * fac[n - i]);
					ret[i] = j;
					visit[j] = true;
					break;
				}
				++cnt;
			}
		}

		for (int i = 1; i <= n; ++i)
		{
			cout << ret[i] << " ";
		}
	}
	else
	{
		ll p = 1;
		for (int i = 1; i <= n; ++i)
		{
			cin >> ret[i];
			ll cnt = 0;
			for (int j = 1; j < ret[i]; ++j)
			{
				if (visit[j] == false) ++cnt;
			}
			p += cnt * fac[n - 1];
			visit[ret[i]] = true;
		}
		cout << p << endl;
	}

	return 0;
}