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

www.acmicpc.net/problem/1722

1722번: 순열의 순서

구현문제였습니다.

 

풀이방법

예제에서 n = 4 소문제 번호가 1인 경우를 예시로 설명하겠습니다.

나올 수 있는 모든 순열의 경우 수는 4!이므로 24개입니다.

 

24개 중 
천의 자리 1로 시작하는 순열들을 1 ~3! 번째 순열 사이에 있습니다.
천의 자리 2는 3! + 1 ~ 3! + 3! + 1! 
천의 자리 3은 3! + 3! +1 ~ 3! + 3! + 3! +1
천의 자리 4는 3! + 3! + 3! +1 ~ 4!

해당 규칙을 이용해 for문 2개로 수를 결정할 수 있다는 것을 알 수 있습니다.

 

소문제 번호가 2인 경우

1 ~ n까지 입력받은 순열의 배열을 순회하면서 ans += (i번째 순열의 수 - 1 - 결정된 j의 개수) * (n-i)!를 하면 답을 구할 수 있습니다.

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, k, op, ans = 1;
ll factorial[21] = {1};
ll ck[21];
int main(){
    cin >> n >> op;
    vector <ll> comb(n+1);
    for(int i = 1; i <= n; i++) factorial[i] = factorial[i-1] * i; 

    if(op == 1){
        cin >> k; //3
        
        for(int i = 1; i <= n; i++){ //i번째 자리
            for(int j = 1; j <= n; j++){ //j수
                if(ck[j]) continue;
                if(factorial[n-i] < k){ //skip마다 n-i!씩 빼줌
                    k -= factorial[n-i];
                }
                else{
                    comb[i] = j;
                    ck[j] = 1;
                    break;
                }
            }
        }

        for(int i = 1; i <= n; i++) cout << comb[i] << ' ';

    }
    else{
        for(int i = 1; i <= n; i++) cin >> comb[i];

        for(int i = 1; i <= n; i++){
            for(int j = 1; j < comb[i]; j++){
                if(ck[j]) continue;
                ans += factorial[n-i];
            }
            ck[comb[i]] = 1;
        }
        cout << ans << '\n';
    }
}