반응형
1722번: 순열의 순서
첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지
www.acmicpc.net
1번 문제
2번 문제
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll arr[21], used[21];
ll n, m;
ll fact[21];
void init_fact() {
fact[0] = 1;
for (ll i = 1; i <= n; i++) {
fact[i] = i * fact[i - 1];
}
}
void func1() {
ll x;
cin >> x;
for (ll i = 1; i <= n; i++) { // 모든 자리 탐색
ll cnt = 1; // 중간에 사용한 것 거르기 위해서 idx, cnt 따로 사용해야 함
for (ll idx = 1; idx <= n; idx++) { // 모든 숫자 탐색
if (used[idx]) // 사용했으면 다음 인덱스 탐색
continue;
if (cnt * fact[n - i] >= x) { // 개수 충분한 지 확인
cout << idx << ' ';
used[idx] = true;
x -= (cnt - 1) * fact[n - i];
break;
}
cnt++;
}
}
}
void func2() {
for (ll i = 1; i <= n; i++)
cin >> arr[i];
ll ans = 1;
ll idx = 1;
while (idx <= n) {
// 현재 idx의 숫자보다 앞에 있는 숫자의 개수 찾기
ll cnt = arr[idx] - 1;
for (ll i = 1; i < arr[idx]; i++) {
// 앞에 있는 숫자가 이미 사용됐으면 cnt--
if (used[i])
cnt--;
}
// (내 앞에 올 수 있는 숫자 개수) * (내 뒤에 올 수 있는 경우의 수)
ans += (cnt * fact[n - idx]);
used[arr[idx]] = 1;
idx++;
}
cout << ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
init_fact();
if (m == 1)
func1();
else
func2();
}
|
cs |
반응형