<링크>
https://www.acmicpc.net/problem/1722
<소스코드>
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 68 69 | #include<stdio.h> #include<algorithm> #include<vector> using namespace std; typedef unsigned long long ull; void setFac(); ull fact[21] = { 1, }; int main() { int N,T; setFac(); scanf("%d", &N); while (~scanf("%d", &T)) { if (T == 1) { ull k; scanf("%llu", &k); vector<int> first; for (int i = 1; i <= N; ++i) first.push_back(i); vector<int> ans; --k; int p = N - 1; while (p>=0) { int div = k / fact[p]; ans.push_back(first[div]); first.erase(first.begin() + div);//벡터지우기 k = k % fact[p]; --p; } for (int i = 0; i < N; ++i) printf("%d ", ans[i]); printf("\n"); } else { int tmp; ull ans = 0; vector<int> v; for (int i = 0; i < N; ++i) { scanf("%d", &tmp); v.push_back(tmp); } for (int i = 0; i < N-1; ++i) { int cnt = v[i]-1; for (int j = 0; j <= i; ++j) { if (v[j] < v[i]) --cnt; } if (cnt > 0) ans += cnt * fact[N - i - 1]; //팩토리얼 더해 } printf("%llu\n", ans + 1); } } } void setFac() { for (int i = 1; i <= 20; ++i) fact[i] = fact[i - 1] * i; } | cs |
<풀이>
1. k번째 순열 구하기
| ull k; scanf("%llu", &k); vector<int> first; for (int i = 1; i <= N; ++i) first.push_back(i); vector<int> ans; --k; int p = N - 1; while (p>=0) { int div = k / fact[p]; ans.push_back(first[div]); first.erase(first.begin() + div);//벡터지우기 k = k % fact[p]; --p; } | cs |
일단 벡터에 1부터 N까지 집어넣는다.
초기에는 {1,2,3,4}이다.
그 후 각 자리마다 몇번째 블록에 해당하는지 알아내면 된다.
k=10일때
맨 앞 숫자의 index를 구하면
k / 3! 이 된다. 왜냐면
1로 시작하는 경우 3!개, 2로 시작하는 경우 3!개, 3으로 시작하는 경우 3!개, 4로 시작하는 경우 3!개가 있기 때문이다.
그럼 k / 3! 의 몫이 곧 맨 앞의 숫자의 index가 된다.
● 첫번째 숫자 구하기
10 / 3! = 1이므로
{1,2,3,4} 의 [1]은 2가 된다.
그 후 2는 이미 나왔으므로 나중에 index를 구했을 때 지장을 주지 않기 위해 빼버린다.
{1,3,4}가 된다.
● 두번째 숫자 구하기
3!단위의 블록이 정해졌으면 그 안에서의 index을 또 찾기 위해 10%3!을 해서 4를 만든다.
4 / 2! = 2이므로
{1,3,4} 의 [2]는 4가 된다. 4를 빼버리고 {1,3}으로 만든다.
● 세번째 숫자 구하기
4%2!을 해서 0을 만들고
0/1! = 0이므로
{1,3}의 [0]은 1이 된다. 1을 빼버리고 {3}으로 만든다.
● 마지막 숫자 구하기
{3}의 [0]은 3이다.
2 4 1 3 이 답이 된다.
2. 순열 입력받아 k 구하기
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | int tmp; ull ans = 0; vector<int> v; for (int i = 0; i < N; ++i) { scanf("%d", &tmp); v.push_back(tmp); } for (int i = 0; i < N-1; ++i) { int cnt = v[i]-1; for (int j = 0; j <= i; ++j) { if (v[j] < v[i]) --cnt; } if (cnt > 0) ans += cnt * fact[N - i - 1]; //팩토리얼 더해 } printf("%llu\n", ans + 1); | cs |
각 숫자를 보면서 내 앞에 몇 개가 있는지 본다. ( 2,4,3,1 )
● 첫번째숫자 : 2
1 x x x 인 애들을 일단 건너뛰어야 한다.
따라서 (2-1) * 3! = 6
● 두번째숫자 : 4
두번째 숫자부터는, 내 앞에 나왔던 숫자 중에 나보다 작은 숫자가 이미 등장했으면 경우의 수로 셀 수 없기 때문에
건너뛸 수 있는 경우의 수에서 제외시킨다.
2 1 x x : 2개
2 2 x x : 2개
2 3 x x : 2개
총 6개를 건너뛰어야 될 것 같지만 2 2 x x 는 순열로 불가능하기 때문이다.
따라서 ( 4 -1- 1 )* 2! = 4
● 세번째숫자 : 3
2 4 1 x 는 가능하지만
2 4 2 x 는 불가능하기 때문에
( 3 - 1 - 1 ) * 1! = 1
6+4+1 = 11이 답이 된다.