[백준][C++]1722번 순열의 순서

문제

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

1722번: 순열의 순서

 

 

풀이

0. 자릿수에 따른 순열의 경우의 수를 1부터 N자리까지 미리 계산

 

1. K번째 순열 출력하기

  ① 주어진 값(K)과 현재 자리(N) - 1에서 만들 수 있는 경우의 수를 비교한다.

  ② ①에서 K가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킨다(순열의 순서를 1씩 늘림). 

  ③ K가 더 작아지면 순열에 값을 저장하고 K를 K - (경우의 수 * (cnt - 1))로 업데이트한다.

  ④ 순열이 완성될 때까지 ①~③을 반복하고 완료된 순열을 출력한다.

 

2. 입력된 순열의 순서 구하기

  ① 현재 자릿수의 숫자를 확인하고 해당 숫자보다 앞 숫자 중 미사용 숫자를 카운트한다.

  ② 미사용 숫자 개수 * (현재 자리 - 1에서 만들 수 있는 순열의 개수)를 K에 더한다.

  ③ 모든 자릿수에 관해 ①~③을 반복한 후 K값을 출력한다.

 

조합(Combination) 알고리즘

조합(Combination) 알고리즘

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N, check;
  cin >> N >> check;

  vector<long long> dp(N + 1, 1);  // 자릿수에 따른 순열의 개수
  // 팩토리얼 초기화
  for(int i = 2; i <= N; i++)
  {
    dp[i] = dp[i - 1] * i;
  }

  vector<bool> visited(N + 1, false);	// 숫자 사용 여부 저장 배열
  vector<int> S(N + 1);	// 순열을 담는 배열
  long long k = 1;
  
  if(check == 1)
  {
    cin >> k;	// 몇 번째 순열을 출력할지 입력받기

    for(int i = 1; i <= N; i++)
    {
      for(int j = 1, cnt = 1; j <= N; j++)
      {
        // 이미 사용한 숫자는 사용할 수 없음
        if(visited[j])
        {
          continue;
        }
        // 주어진 k에 따라 각 자리에 들어갈 수 있는 수 찾기
        if(k <= dp[N - i] * cnt)
        {
          k -= dp[N - i] * (cnt - 1);
          S[i] = j;	// 현재 자리에 j값 저장
          visited[j] = true;	// 숫자 j를 사용 숫자로 체크
          break;	// 반복문 종료
        }
        cnt++;
      }
    }

	// 배열 출력
    for(int i = 1; i <= N; i++)
    {
      cout << S[i] << " ";
    }
  }
  // 순열의 순서를 출력하는 문제
  else if(check == 2)
  {
    for(int i = 1; i <= N; i++)
    {
      cin >> S[i];
    }
    
    for(int i = 1; i <= N; i++)
    {
      int cnt = -1;
      for(int j = 1; j <= S[i]; j++)
      {
        // 미사용 숫자 개수만큼 카운트
        if(!visited[j])
        {
          cnt++;
        }
      }
      visited[S[i]] = true;	// S[i]번째 숫자를 사용 숫자로 변경
      k += (cnt * dp[N - i]);	// 자릿수 개수에 따라 순서 더하기
    }

    cout << k;	// k 출력
  }
  
  return 0;
}

 

 

오답

1. K번째 순열 출력하기

• j : 해당 자리에 저장할 숫자 변수 ⇒ 이미 사용한 숫자는 사용할 수 없음
• cnt : 해당 자리에서 몇 번째 숫자를 사용해야 할 지 정하는 변수

 

#include <iostream>
using namespace std;

static int N, Q;
static long F[21], S[21];
static bool visited[21] = {false};

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> N >> Q;
  F[0] = 1;
  // 팩토리얼 초기화 -> 각 자릿수에서 만들 수 있는 경우의 수
  for(int i = 1; i <= N; i++)
  {
    F[i] = F[i - 1] * i;
  }
  if(Q == 1)
  {
    long K;
    cin >> K;

    for(int i = 1; i <= N; i++)
    {
      for(int j = 1, cnt = 1; j <= N; j++)
      {
        // 이미 사용한 숫자는 사용할 수 없음
        if(visited[j])
        {
          continue;
        }
        // 주어진 K에 따라 각 자리에 들어갈 수 있는 수 찾기
        if(K <= cnt * F[N - i])
        {
          K -= ((cnt - 1) * F[N - i]);
          S[i] = j;
          visited[j] = true;
          break;
        }
        cnt++;
      }
    }
    for(int i = 1; i <= N; i++)
    {
      cout << S[i] << " ";
    }    
  }
  else
  {
    long K = 1;

    for(int i = 1; i <= N; i++)
    {
      cin >> S[i];
      long cnt = 0;

      for(int j = 1; j < S[i]; j++)
      {
        // 미사용 숫자 개수만큼 카운트
        if(visited[j] == false)
        {
          cnt++;
        }
      }
      K += cnt * F[N - i];  // 자릿수 개수에 따라 순서 더하기
      visited[S[i]] = true;
    }
    cout << K << "\n";
  }
  
}

 

[ 정답코드 예시 ]

N = 4, K = 3인 경우

0. 자릿수에 따른 순열의 경우의 수 (1 ~ N 자리) : 1, 2, 6, 24

 

1. K번째 순열 출력하기

① K(3) ≤ 6 * 1

  ⇒ K = K - (6 * (cnt - 1))

    = K - (6 * (1 - 1)) = 3

② K(3) > 2  * 1

  K(3) ≤ 2 * 2

  ⇒ K = K = K - (2 * (cnt - 1))

    = K - (2 * (2 - 1)) = 1

③ K(1) ≤ 1 * 1

④ 남아 있는 수 입력 후 순열 출력

 

2. 입력된 순열의 순서 구하기

① 현재 자릿수의 숫자 : 1

  ⇒ 현재 수 중 1번째이므로 K값을 갱신하지 않음

  ⇒ K = 1

② 현재 자릿수의 숫자 : 3

  ⇒ 3보다 작은 미사용 숫자(2)가 1개 존재하므로 K값을 갱신

  ⇒ K = K + F[2] * (미사용 숫자 개수)

    = K + F[2] * 1 = 3

  ⇒ K = 3

③ 현재 자릿수의 숫자 : 2

  ⇒ 현재 수 중 1번째이므로 K값을 갱신하지 않음

  ⇒ K = 3

④ 현재 자릿수의 숫자 : 4

  ⇒ 현재 수 중 1번째이므로 K값을 갱신하지 않음

  ⇒ K = 3