이번 문제는 사실상 조합을 찾아내는 문제입니다. 그런데 조합을 찾기 위한 숫자가 좀 큽니다. 그래보았자, 100이지만요.
난이도는 Gold IV입니다. 정답률은 28.5%이긴 하지만, 크게 어렵지 않았다고 생각했습니다.
문제의 내용을 정리하자면, 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} \) 까지의 조합을 구합니다.
\[ _nC_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 \lt ~_iC_m \) 라면 오른쪽에서 i번째 자리는 a가 와야 합니다. 그렇지 않다면, z를 출력하고 m을 하나 줄이고 K 값을 \(_iC_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');
}
'Programming > BOJ' 카테고리의 다른 글
#1276 교각 놓기(정렬) (2) | 2020.01.14 |
---|---|
[C/C++] 백준 #1275 커피숍2(세그먼트 트리) (0) | 2020.01.14 |
백준 #1254 팰린드롬 만들기 (0) | 2020.01.12 |
백준 #1253 좋다 (0) | 2020.01.11 |
백준 #1244 스위치 켜고 끄기 (0) | 2020.01.11 |
댓글