#1256 사전(Combination Digit)

이번 문제는 사실상 조합을 찾아내는 문제입니다.  그런데 조합을 찾기 위한 숫자가 좀 큽니다.  그래보았자, 100이지만요.

난이도는 Gold IV입니다.  정답률은 28.5%이긴 하지만, 크게 어렵지 않았다고 생각했습니다.

 

az

 

문제의 내용을 정리하자면, N개의 a 문자와 M개의 z 문자를 조합하여 사전순으로 배열할 때, K번째 문자열을 출력하는 문제입니다.

예를 들어서 3개의 a와 2개의 z가 있다면 다음과 같이 사전순으로 나열할 수 있습니다.

 

aaazz

aazaz

aazza

azaaz

azaza

azzaa

zaaaz

zaaza

zazaa

zzaaa

 

이렇게 해서 총 10개의 문자열이 나옵니다.  10개의 문자열이 나온 이유는 5개의 공간 중에 2개의 공간을 선택해서 그곳에 z를 채우고, 나머지 공간에는 a로 채우면 됩니다.  즉 총 경우의 수는 ${}_{N+M}{C}_M$ 이 됩니다.  위의 경우에는 5개중에 2개를 선택하는 것이니까, 10가지가 나왔습니다.

 

K번째 문자열을 고르기 위해서는 조합을 구해야 할 것이 꽤 많습니다.  그래서 미리 ${}_1{C}_1$ 부터 ${}_{N+M}{C}_M$ 까지의 조합을 구합니다.

 

$${}_n{C}_m={}_{n-1}{C}_m+{}_{n-1}{C}_{m-1}$$

 

위의 공식을 구하면 파스칼의 삼각형처럼 조합을 순차적으로 구할 수 있습니다.  당연히 중간 계산과정에서 숫자가 넘어가는 경우가 생깁니다.  아마 정답률이 낮은 이유 중에 숫자 범위를 벗어나서 고민한 사람들이 있을겁니다.  하지만 K값이 ${10}^9$ 이하로 주어지기 때문에 숫자값이 넘치는 경우에는 숫자를 제한시켜주면 됩니다.  속편하게 long long으로 처리한 사람들도 있었겠지만, 아마도 틀렸습니다가 나왔을겁니다.  K가 int 범위인데, 안 넘어갈거라고 생각했을 수도 있겠죠.  대충 계산해보면, ${}_{100}{C}_{50}\approx {10}^{29}$이니까요.

 

이제 a와 z를 배치하는 방법입니다.

 

$K<{}_i{C}_m$ 라면 오른쪽에서 i번째 자리는 a가 와야 합니다.  그렇지 않다면, z를 출력하고 m을 하나 줄이고 K 값을 ${}_i{C}_m$만큼 줄입니다.  이 방식으로 하면 원하는 문자열을 출력할 수 있습니다.  마치 자릿수에 수를 배치하는 것과 비슷합니다.  조합 자릿수라고 생각하시면 될 듯 하네요.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//--------------------------------------------------------------------
//  baekjoon #1256 - Dictionary
//    - by Aubrey Choi
//    - created at 2019-07-12
//--------------------------------------------------------------------
#include <stdio.h>

int main()
{
  int comb[201][101];
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  comb[0][0] = 1;
  for(int i = 1; i <= n + m; i++)
  {
    comb[i][0] = 1;
    for(int j = 1; j < i && j <= m; j++)
    {
      comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
      if(comb[i][j] > 1000000000) comb[i][j] = 1000000000;
    }
    if(i <= m) comb[i][i] = 1;
  }
  k--;
  if(comb[n + m][m] <= k) { puts("-1"); return 0; }
  for(int i = m + n - 1; i >= 0; i--)
  {
    if(i >= m && comb[i][m] > k) putchar('a');
    else
    {
      putchar('z');
      k -= comb[i][m];
      m--;
    }
  }
  putchar('\n');
}