백준[1722] - 순열의 순서

문제

백준 1722 문제 보기

접근 방법

순열의 길이가 큰 관계로 최대 20!의 값을 가진다. 즉, 모든 경우를 해보면서 답을 출력하기는 적절하지 않다. 따라서 약간의 수학적 접근으로 문제를 해결한다.
순열의 길이가 10이라고 가정을 한다면 {1, 2, 3, …}, {1, 3, 2, …}, {1, 4, 2, …} 이런식으로 올 수 있는 경우의 수가 9!이다. 따라서 9!보다 구하려는 숫자가 작다면 맨앞의 숫자는 {1, …} 이런식으로 나타날 것이다. 이를 활용해 미리 20!까지의 수를 구해놓고 문제를 해결할 수 있다.

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int N, in;
long long cnt;
long long ans = 0;
long long factorial[21];
int use[21];
vector<int> v(N);

int main() {
    cin >> N;
    cin >> in;

    memset(use, 0 , sizeof(use));

    factorial[0] = 1;
    // 팩토리얼 미리 구해 놓기
    for(int i = 1; i < 21; i ++) {
        factorial[i] = factorial[i - 1] * i;
    }

    switch (in) {
        case 1:
            cin >> cnt;
            for(int i = 0; i < N; i ++) {
                for(int f = 1; f <= N; f ++) {
                    // 사용했다면 패스
                    if(use[f] == 1)
                        continue;
                    // 구하려는 cnt보다 팩토리얼이 작을 경우
                    if(factorial[N - i - 1] < cnt) {
                        cnt -= factorial[N - i - 1];
                    } else {
                        v.push_back(f);
                        // 숫자 사용 여부 체크
                        use[f] = 1;
                        break;
                    }
                }
            }

            for(int i = 0; i < N; i ++) {
                cout << v[i] << " ";
            }
            break;

        case 2:
            for(int i = 0; i < N; i ++) {
                int t;
                cin >> t;
                v.push_back(t);
            }

            for (int ii = 0; ii < N; ii++) {
                for (int j = 1; j < v[ii]; j++) {
                    if (use[j] == 0) {
                        ans += factorial[N - ii - 1];
                    }
                }

                use[v[ii]] = 1;
            }

            cout << ans + 1 << '\n';
            break;
    }
    return 0;
}