<문제 링크>
https://algospot.com/judge/problem/read/DICT
문제
(주의: 이 문제는 TopCoder SRM428 Div2 Hard 의 번역 문제입니다.)
a 와 b 로만 이루어진 단어들을 담고 있는 사전이 있다. 이 사전은 n 개의 a 와 m 개의 b 로 이루어진 단어들을 _전부_ 포함하는데, 예를 들어 n=2, m=2 인 경우, 사전에는 aabb, abba 등의 단어들이 포함된다.
n 과 m 이 주어질 때, 이 사전의 k 번째 단어를 출력하는 프로그램을 작성하라. 단어들은 사전 순서대로 정렬되어 있다고 가정한다.
입력
입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에 n, m (0 <= n, m <= 100) 그리고 k (1 <= k <= 100,000,000) 가 주어진다.
출력
각 테스트 케이스마다 사전의 해당 단어를 한 줄에 출력한다. 만약 사전의 k 번째 단어가 없을 경우 (사전의 단어 수가 k 보다 적을 경우) 에는 NONE 을 출력한다.
본 문제는 조합의 값을 구해야된다. 이때 조합을 한개 한개 구하는 함수를 만들면 조합의 값을 구하는 오버헤드가 너무 커진다. 이를 해결하가위해 필요한 조합의 값을 파스칼의 삼각형을 이용하여 미리 다 구해 놓는다. 우리는 (n + m)^2개의 조합을 구해야 하고 각 조합의 값을구하는 대는 덧셈 한번 즉 O(1)의 시간복잡도가 소요된다. 그러므로 O((n+m)^2)의 시간복잡도를 소요한다.
이제 구해놓은 조합의 값으로 문제를 해결해야된다. n개의 a가 있고 m개의 b가 있을때 사전순으로 가장 먼저오는 경우는 aa..aa(n개)bb..bb(m개)이다. 가장 먼저 오는 경우 같은 경우 n개의 a가 연속이고 그다음으로는 m개의 b가 연속이다. 이때 앞에 n개이 원소들과 뒤의 m개들의 원소들을 분리해서 생각해보자. 위의 m개들의 원소들로 만들 수 있는 모든 경우의 순열은 bb..bb 한 가지다. 이는 앞의 n개원소가 전부 a일때에는 만들수있는 순열의 수가 1가지라는 것이다. 지금 우리가 만든 순열보다 사전순으로 앞서는 순열은 존재하지 않는다. 만약 입력에서 k의 값이 1보다 크다면 n개의 원소가 전부 a인 경우는 답이 될 수 없다. 그렇다면 우리는 앞의 n개의 원소가 모두 a인 경우는 정답에서 제외시킨다. 그다음으로 고려해야될 순열은 첫번째 인덱스부터 n-1번째 인덱스까지 a가있고 n번째인덱스에 b가있는 순열이다. 그렇다면 다음으로 오는 m개의 원소에는 m - 1개의 b와 1개의 a가 있다. 이때 m개의 원소로 만들수있는 순열의 경우의 수는 mC1이다. 만약 k가 mC1보다 크다면 n개의 원소가 지금과 같은 순열은 정답이 될수가 없다. 그렇다면 k를 mC1만큼 감소시키고 다음의 경우를 본다. 다음의 경우는 첫번째 인덱스부터 n-2번째 인덱스 까지 연속된 a와 n-1과 n이 b인 n개의 원소가 앞에있고 뒤에 2개의 a와 m - 2개의 b가있는 순열이다. 이때만들수있는 순열의 경우의수는 m + 1C2이다. 이때 k가 m+1C2보다 크다면 앞의 과정을 계속 반복하면 된다. 만약 k 가 m+1C2보다 작거나 같다면 정답은 우리가 지금 고려하고있는 n개의 원소뒤에 2개의 a와 m-2개의 b가 만들 수 있는 경우 중에서 정답이 있다는 뜻이다. 그렇다면 우리는 이를 해결하기 위해서 재귀함 수를 이용할 수 있다. 여기서 새로운 부분문제를 풀면 되는것이다. 2개의 a와 m - 2개의 b와 현재 k를 입력으로 받은 새로운 문제의 정답을 구하면 되는 것이다. 그리고 n개의 a와 m개의 b가 만들수 있는 모든 경우의 수는 m+nCn 이며 k가 이보다 크면 정답을 구할 수 없기 때문에 NONE를 출력한다.
구현에 있어서 n, m의 범위를 고려할때 n+m은 최댓값이 200이다. 200C100을 구해서 변수에 저장한다고 가정했을때 이는 필히 부동소수점 표현이 아닌이상 오버플로우가 발생 한다. 이를 해결할 수 있는 방법은 k의 상한이 1억 이므로 1억보다 큰 조합의 값들은 모두 1억+1로 저장한다. 이렇게 구현하면 k와 비교하는데 있어서 원래의 조합값이나 현재 1억+1의 값이나 어짜피 k보다 크기때문에 원래의 조합값으로 계산했을때와 동일한 결과치를 얻을 수 있다.
문제를 해결하는 코드는 아래와 같다.
#include<iostream>
#include<string>
using namespace std;
string kth(int numA, int numB, int remain);
int n, m, k;
int c[201][201];
int main() {
int cases;
cin >> cases;
for (int i = 0; i <= 200; ++i) {
c[i][0] = c[i][i] = 1;
c[i][1] = i;
}
for (int i = 2; i <= 200; ++i)
for (int j = 2; j < i; ++j) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
if (c[i][j] > 100000000)
c[i][j] = 100000001;
}
while (cases--) {
cin >> n >> m >> k;
if (c[n + m][n] < k || (n == 0 && m == 0)) {
cout << "NONE" << endl;
continue;
}
cout << kth(n, m, k) << endl;
}
}
string kth(int numA, int numB, int remain) {
if (remain == 1) {
string ret = "";
for (int i = 0; i < numA; ++i)
ret += "a";
for (int i = 0; i < numB; ++i)
ret += "b";
return ret;
}
for (int i = 0; i <= numA; ++i) {
if (c[numB + i - 1][i] < remain)
remain -= c[numB + i - 1][i];
else {
string ret;
for (int j = 0; j < numA - i; ++j)
ret += "a";
return ret + "b" + kth(i, numB - 1, remain);
}
}
return "error";
}