[백준 1722] 순열의 순서

www.acmicpc.net/problem/1722

1722번: 순열의 순서

n=20이기 때문에 백트래킹으로 전부 확인했다가는 tle가 뜨는 문제

 

순열의 개념과 dp를 사용해야 한다.

고등학교 수학 문제에 자주 등장하는 문제 중 하나인데 그 때의 풀이법을 살펴보자.

 

n = 4이고 10번째 순열을 구하라 라는 문제가 있으면

1 2 3 4 : 4개의 숫자를 사용할 수 있고 앞자리 부터 차례로 3! 2! 1!을 계산해볼 것이다.

 

k = 10가 3!보다 크다는 의미는 맨 앞자리 1이 2로 바뀐다는 의미이다.

2 _ _ _

그리고 2134는 3! + 1 = 7번째 순열이 된다. k -= 3!을 하면 k = 4가 된다.

 

k  < 3!이므로 다음 2!를 고려한다.

 

k > 2!이므로 2 1 3 4 에서 두 번째 자리인 1이 다른 숫자 3으로 바뀔 것이다.

2 3 _ _

그리고 2 3 1 4는 3! + 2! + 1 = 9번째 순열이 된다.  k -= 2! 하면 k = 2가 된다.

 

k < 2! 이므로 다음 1!을 고려한다.

 

k > 1!이므로 세 번째 자리인 1이 다른 숫자 4로 바뀔 것이다.

2 3 4 _

k -= 1!하면 k = 1이 된다.

2 3 4 1이 10번째에 해당하는 순열임을 알 수 있다. 

 

알고리즘으로 정리하면 k가 어떤 자리수 i!보다 크다는 의미는 n-i-1 자리의 숫자가 변한다는 의미이다.

반대로 k가 어떤 자리수 i!보다 작다는 의미는 n-i-1 자리의 숫자는 고정이라는 의미이다.

 

그래서 우리는 

1. 먼저 factorial 숫자를 fac에 저장하고

2. i는 결과 벡터의 인덱스

3. j는 결과 벡터 인덱스에 들어갈 값을 나타낼 것이다.

 

factorial 배열은 거꾸로 돌며 k보다 작아지는 시점에 k에서 빼준다.

k보다 크다는 의미는 해당 위치의 숫자가 고정된다는 의미이다. 

그래서 결과 위치 i에 값 j를 넣고 j에 사용했다는 표시를 해준다.

팩토리얼 값이 k보다 작아지면 k값을 빼주고 다음 숫자로 넘어간다.

    for (int i = 0; i < n; i++)
    {
      for (int j = 1; j <= n; j++)
      {
        if (visited[j])
          continue;
        if (k > fac[n - i - 1])
        {
          k -= fac[n - i - 1];
        }
        else
        {
          v[i] = j;
          visited[j] = 1;
          break;
        }
      }
    }

 

#include <stdio.h>
#include <vector>

using namespace std;
int n, com;
long long k;
long long fac[20];
int visited[20];

int main(void)
{
  scanf("%d%d", &n, &com);

  // 자리에 따라 만들 수 있는 숫자 경우의수를 계산합니다.
  fac[0] = 1;
  for (int i = 1; i <= n; i++)
  {
    fac[i] = i * fac[i - 1];
  }
  vector<int> v(n);

  if (com == 1)
  {
    scanf("%lld", &k);

    for (int i = 0; i < n; i++)
    {
      for (int j = 1; j <= n; j++)
      {

        if (visited[j])
          continue;
        if (k > fac[n - i - 1])
        {
          k -= fac[n - i - 1];
        }
        else
        {
          v[i] = j;
          visited[j] = 1;
          break;
        }
      }
    }

    for (int i = 0; i < n; i++)
    {
      printf("%d ", v[i]);
    }
    printf("\n");
  }
  else
  {
    long long result = 0;
    for (int i = 0; i < n; i++)
    {
      scanf("%d", &v[i]);
    }

    for (int i = 0; i < n; i++)
    {
      for (int j = 1; j < v[i]; j++)
      {
        if (visited[j])
          continue;
        result += fac[n - i - 1];
      }
      visited[v[i]] = 1;
    }

    printf("%lld\n", result + 1);
  }

  return 0;
}