Tip - 순열의 인덱스와 K번 째 순열
BOJ 1722 - 순열의 순서 문제를 해결하는 방법을 설명한다.
- 길이 $N$의 순열의 $K$ 번째 순열을 구하는 것
- 길이 $N$의 순열이 주어졌을 때 그것이 몇 번째인지를 구하는 것
은 간혹 DP문제에서도 인덱스를 치환하는 것이 쓰이며, 꽤나 요긴한 팁라고 할 수 있다.
순열이 몇 번째인지 구하기
길이가 $N=5$이라고 하자.
$1,2,3,4,5$ 같은 순열은 $1$번 째 순열이다.
정의를 깔끔하게 하기 위해 $K$번 째 수열이라고 하지 않고 $K-1$개를 skip한 후의 수열이라고 부르자.
수열이 $3,x,x,x,x$ 처럼 되어있다고 하자.
그럼 $1,x,x,x,x~or~2,x,x,x,x$ 같은 순서를 이미 skip했다는 것이고, 그런 순열의 개수는 $4!$ 이 두 번 곱해져서 $2\cdot 4!$ 임을 알 수 있다.
따라서 이걸 정답에 더해준다.
그런데 이것이 첫 번째 인덱스가 아니고,
$y,3,x,x,x$ 같은 경우라고 해보자.
$y$ 는 이미 정해진 값이다. 원래 순열이 주어져있으므로 정해져 있는건 맞지만 저 자리에 $y+1$ 이상이면 $K$ 보다 많이 skip 해야하기 때문에 다음 인덱스$(i=0 \to i=1)$를 검사하기 시작했다는 뜻이다.
그럼 $x$ 중에서 $3$ 보다 작은 수의 개수를 세야한다. 아직 안 사용한 수를 보면 $3,x,x,x$ 뿐이고, 여기서 $3$ 보다 작은 것의 개수가 길이 3짜리 순열을 skip한 개수이다.
따라서 $x\text{중에서 3보다 작은 } x\text{의 개수} \cdot 3!$ 을 정답에 더해준다.
이런식으로 모든 인덱스를 순회하면 몇개를 skip한 순열인지 구해진다.
따라서 순열의 순서는 구해진 정답(skip한 개수)에 1을 더해주면 된다.
vi a(n);
fv(a);
// 몇 번째 순열인지 찾는다.
int ans = 0;
for (int i = 0; i < n; i++) {
int less = 0;
for (int j = i + 1; j < n; j++) if (a[j] < a[i]) less++;
ans += fac[n - 1 - i] * less;
}
cout << ans + 1;
$K$ 번째 순열 구하기
또 팩토리얼을 이용하면 된다.
여기서는 이제 지금까지 안 쓴 값을 배열로 직접 관리한다. 이걸 remain 이라고 하자.
$K$는 $K \coloneqq K-1$ 을 해준다. 왜냐면 $K$ 번 째를 구하는게 아닌 $K$ 개를 스킵한 후의 결과를 구하기 위함이다.
처음엔 $1$부터 $N$까지 모두 넣어두고, 처음 자리에 뭐가 들어가야할 지 구한다고 해보자.
지금까지 안 쓴 수중에 $\left\lfloor\dfrac K{(N-1)!}\right\rfloor$ 개를 스킵할 수 있으므로,
$remain\left[\left\lfloor \dfrac K{(N-1)!} \right\rfloor\right]$ 를 이번에 써야 할 수로 정해주고 $remain$ 에서 그 수를 지워주면 된다.
이후 $K$ 는 그만큼 skip한 것이므로 $\left\lfloor \dfrac K{(N-1)!} \right\rfloor\cdot (N-1)!$ 만큼 빼줄 수 있다.
$0!=1$ 이므로 denominator=0 이 될 일은 없다.
int k;
cin >> k;
k--;
// k 번째 순열을 찾는다.
vi remain(n);
iota(all(remain), 1);
vi ans;
for (int i = 0; i < n; i++) {
int f = fac[n - 1 - i];
ans.pb(remain[k / f]);
k -= k / f * f;
remain.erase(find(all(remain), ans.back()));
}
for (int i: ans) cout << i << ' ';
Comments