BOJ 1722

03 Apr 2020 • ProblemSolving

순열의 순서

문제출처

문제 해석

  • N!가지의 순열 중 K번째 순열 또는 특정 순열이 몇번째 순열인지 맞추는 문제입니다.

설계(20)

  • 생각보다 까다로웠던 문제였습니다.
  • 우선, factorial값(<=20)을 구해놓습니다.
  • 주어지는 입력이 1번인 경우 K번째 순열을 찾아야 합니다.
  • 재귀함수를 이용하여 K보다 큰 인덱스가 나올때까지 factorial(N-1)을 더해줍니다.
  • 예를 들어, 4!기준 15번째 순열을 찾고자 할 때 “1 x x x”인 경우의 수는 3!= 6가지입니다.
  • 그러면, 15번째 순열보다 작기 때문에 맨 앞에 1이 들어갈 수 없습니다.
  • 계속 진행했을 때 “1 x x x” ~ “3 x x x”인 경우는 총 18가지로 맨 앞에 3이 나오지 않고 바로 아래의 2가 들어가는 것을 확인 할 수 있습니다.
  • 이런식으로 재귀를 이용하여 모든 x가 채워질 때까지 반복하면 원하는 순열을 얻을 수 있습니다.
  • 반대로, 순열이 주어지고 몇번 째 순열인지 맞추는 문제의 경우에는 1~N을 탐색하면서 아직 사용하지 않은 숫자가 있는 경우 원하는 숫자가 나올때까지 (N-1)!씩 더해줍니다.
  • 이를 재귀함수로 반복하면 몇번째 순열인지 알 수 있습니다.

구현(40)

코드
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 21
typedef unsigned long long ll;

ll num[MAXN];
bool used[MAXN];
int arr[MAXN];
int N,idx;
ll t_idx;
bool flag;
int ans_arr[MAXN];
ll ans;

void Find_Idx(int len, ll cnt){
    if (flag) return;
    if (len == N){
        ans = cnt+1;
        flag = true;
        return ;
    }
    ll sum = 0;
    for (int i = 1; i<= N; i++){
        if (used[i]) continue;
        if (arr[len] == i){
            used[i] = true;
            Find_Idx(len + 1, cnt + sum);
        }
        sum += num[N-len-1];
    }
}
void Find_Perm(int len, ll cnt){
    if (flag) return;
    if (len == N){
        flag = true;
        return;
    }
    ll sum = cnt;
    for (int i = 1; i <=N; i++){
        if (used[i]) continue;
        if (sum + num[N-len-1] > t_idx){
            ans_arr[len] = i;
            used[i] = true;
            Find_Perm(len+1,sum);
        }
        sum += num[N-len-1];
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    num[0] = 1;
    for (int i =1; i < MAXN; i++){
        num[i] = num[i-1]*i;
    }
    cin >> N >> idx;
    if (idx == 2){
        for (int i = 0; i<N; i++){
            cin >> arr[i];
        }
        Find_Idx(0,0);
        cout << ans <<"\n";
    }
    else{
        cin >> t_idx;
        Find_Perm(0,1);
        for (int i = 0; i <N; i++){
            cout << ans_arr[i] <<" ";
        }
    }
    return 0;
}
디버깅
  • 1번의 경우에 파라미터를 넣을 때, {0,0}을 넣는 실수를 하였습니다. 4!기준 맨 처음 1 2 3 4는 인덱스가 1이기 때문입니다.
  • 또한, 순열의 인덱스 t_idx를 int형으로 선언하는 실수를 하였습니다. 최대 20!에서 인덱스를 찾기 위해서는 long long형을 선언해야합니다.
제출결과
  • 0 ms

마무리

  • 재귀함수를 이용한 수학문제였습니다. solved.ac 기준 실버치고는 꽤 애를 먹었던 문제였습니다.
 BOJ

Related Posts