백준 1722번: 순열의 순서 (C++)

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

1722번: 순열의 순서

---

Solved By: Combinatorics, Math, DP

소문제가 2개라 유사한 문제 2개를 푸는 것 같았습니다. naive 하게 백트래킹으로 모든 순열을 구하기에는 O(N!)으로 시간 초과가 납니다. 그렇기 때문에 다음과 같은 특징을 찾아야 합니다.

N = 4인 순열에서 3번째 순열을 찾으라고 하면
첫 순열이 {1, X, X, X}로 시작하는 것을 알고, 나머지 X에 올 수 있는 조합이 3!(= 6)개이기 때문에 {1, 2, X, X}까지는 주고 다시 조합을 찾습니다.
여기서는 나머지 X에 올 수 있는 조합이 2!(= 2)개이기 때문에 {1, 3, X, X}로 시작합니다. 여기서도 나머지 X에 올 수 있는 조합은 2개라 {1, 4, X, X}를 주면 5번째 순열부터 찾는 꼴이 되어버리므로 {1, 3, 2, X}로 둡니다.
나머지는 4로 채워지기 때문에 3번째 순열 {1, 3, 2, 4}를 찾게 됩니다.

풀이는 조금 생각하면 풀리지만 코드로 표현하는 게 좀 어려웠던 문제였습니다.
1 ~ 20까지의 팩토리얼은 DP를 통해 구해줍니다.

#include <iostream>
#include <vector>
#define ll long long
#define MAX 21
using namespace std;

ll f[MAX];
ll k;
int N;

int main(){
    cin >> N;
    
    // get Factorial
    f[0] = 1;
    for(int i = 1; i <= N; i++){
        f[i] = f[i - 1] * i;
    }
    
    int c; cin >> c;
    if(c == 1){
        cin >> k;
        vector<int> ans(N + 1, 0);
        // 중복을 하면 안 됨
        vector<bool> visited(N + 1, 0);
        
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                if(visited[j]) continue;
                
                if(f[N - i] < k){
                    k -= f[N - i];
                }
                else{
                    ans[i] = j;
                    visited[j] = true;
                    break;
                }
            }
        }
        
        for(int i = 1; i < ans.size(); i++){
            cout << ans[i] << ' ';
        }
    }
    else{
        // 몇 번째 순열인가
        vector<int> perm(N + 1, 0);
        
        // 중복을 하면 안 됨
        vector<bool> visited(N + 1, 0);
        for(int i = 1; i <= N; i++){
            cin >> perm[i];
        }
        
        ll ans2 = 0;
        for(int i = 1; i <= N; i++){
            for(int j = 1; j < perm[i]; j++){ // 사전순으로 1부터 시작
                if(!visited[j]){
                    ans2 += f[N - i];
                }
            }
            visited[perm[i]] = true;
        }
        
        cout << ans2 + 1;
    }
    
    return 0;
}